\documentclass[%
	a4paper,
	oneside,
	11pt
]{scrreprt}

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphics}

\usepackage{float}
\usepackage{url}

\usepackage{algorithmic}
\usepackage{listings}
\usepackage{tabularx}



%########### text formatting #############################################
\usepackage{scrpage2}
\usepackage[T1]{fontenc}
\usepackage[ngerman]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{textcomp}

\usepackage{setspace}
\onehalfspacing 
\parindent 0pt
%#########################################################################

%########### hyphenation ################################################
\sloppy
 \hyphenation{To-pic To-pics Asso-ci-a-tion Asso-ci-a-tions Roles Subject Oc-cur-rence Oc-cur-rences
 unter-suchten Abschn be-trach-tet be-trach-teten Spe-zi-fi-ka-ti-on Spe-zi-fi-ka-ti-o-nen 
 spe-zi-fi-zier-en spe-zi-fi-ziert Stan-dar-di-sierung je-wei-lig je-wei-ligen je-wei-liger je-wei-lige ei-ner
 ei-ne ei-nes ei-nem Ope-ra-toren Ope-ra-tio-nen zwei-ten zwei-te könn-te Men-gen meng-en-the-o-re-tisch
 meng-en-the-o-re-tischen The-o-re-tisch the-o-re-tischen Ent-spre-chung ent-spre-chend Ent-spre-chungen
 bie-tet bie-ten Bie-ter bie-ten-den bie-ten-der bie-ten-des Ver-ei-ni-gung li-ne-ar li-ne-are
}
%#########################################################################


%########### clickable references to cites and chapters ##################
\usepackage{hyperref}
\hypersetup{backref,    
    colorlinks=true,
    linkcolor=black,
    citecolor=black,
    filecolor=black,
    urlcolor=black,}
%#########################################################################     


%########### itemize listings have no big spaces: ########################
\renewenvironment{itemize}%
{\begin{list}{\textbullet}%
    {\topsep=0in\itemsep=0in\parsep=0in\partopsep=0in\usecounter{enumi}}%
  }{\end{list}}
%###################### enumerate env:
\renewenvironment{enumerate}%
{\begin{list}{\arabic{enumi}.}%
    {\topsep=0in\itemsep=0in\parsep=0in\partopsep=0in\usecounter{enumi}}%
  }{\end{list}}
%#########################################################################


%########### fancy definition style with lines to the left: ##############
\newtheoremstyle{definition}% name
{0pt}%Space above
{0pt}%Space below
{\leftskip0.7em\sffamily}%Body font
{0em}%Indent amount 1
{\bfseries}% Theorem head font
{}%Punctuation after theorem head
{\newline}%Space after theorem head 2
{}%Theorem head spec (can be left empty, meaning ‘normal’)
\theoremstyle{definition}
\newtheorem{definition}{Definition}[chapter]

\usepackage{tikz}
\usetikzlibrary{arrows,fit,shapes.misc}
\newcommand\marktopleft[1]{%
    \tikz[overlay,remember picture] 
        \node (marker-#1-a) at (0em,-0.3) {};%
}
\newcommand\markbottomright[1]{%
    \tikz[overlay,remember picture] 
        \node (marker-#1-b) at (0em,0.55) {};%
    \tikz[overlay,remember picture,thick,gray,inner sep=0pt]
        \draw[gray,thick] (marker-#1-a.center) -- (marker-#1-b.center);%
}
%#########################################################################


%########### Java code listings ##########################################
\lstdefinestyle{java}{language=Java, numbers=left, numberstyle=\tiny,%
stepnumber=1, numbersep=5pt, , frame=l, backgroundcolor=\color{white},%
rulecolor=\color{black}, tabsize=2, breaklines, basicstyle=\small,%
commentstyle=\footnotesize, breakatwhitespace}
%#########################################################################
%Huge,huge,LARGE,Large,large,normal,small,footnotesize,scriptsize,tiny

%########### XML code listings ###########################################
\lstdefinelanguage{XML} {morekeywords={xml,topic,result,%
reference, si, name, parent, type, value, scope, variant,%
datatype, occurrence, occurrence, si, <, >, sl, ii, kiferdkf}
sensitive=false
}
\lstdefinestyle{xml}{language=XML, numbers=left, numberstyle=\tiny,%
stepnumber=1, numbersep=5pt, , frame=l, backgroundcolor=\color{white},%
rulecolor=\color{black}, tabsize=2, basicstyle=\small,%
breaklines, breakatwhitespace}
%#########################################################################


% Title Page
\title{Identifikation und Berechnung von Unterschieden und Gemeinsamkeiten von Topic Maps}
\author{Stephan Felke}


\begin{document}
\maketitle

\newpage
\begin{abstract}
\textit{Abstract}\\

In dieser Arbeit wird gezeigt, wie Unterschiede zweier \textit{Topic Maps} bestimmt und\linebreak effizient berechnet 
werden können. Es wird ein Überblick über das Topic Maps Datenmodell gegeben und aufgezeigt, welche Schritte
notwendig sind, um einen \mbox{umfassenden} Überblick über die Gemeinsamkeiten und Unterschiede zweier 
\textit{Topic Maps} zu\linebreak erlangen. 
Es wird erörtert, wie sich konzeptionelle von sogenannten atomaren \mbox{Unterschieden} abgrenzen lassen.
Unterschiede auf atomarer Ebene beziehen sich auf\linebreak Eigenschaften bestimmter 
Objekte, wohingegen auf struktureller Ebene die Objekte an sich und deren Beziehungen betrachtet werden.
Außerdem wird erklärt, wie beide\linebreak Begriffe voneinander getrennt und im Zusammenspiel betrachtet werden können. 
Hierzu werden Operatoren entwickelt, welche auf \textit{Topic Maps} als Operanden arbeiten und im \linebreak Ergebnis 
die Unterschiede auf konzeptioneller und atomarer Ebene darstellen, ohne dabei den semantischen Mehrwert 
des Topic Maps Datenmodells zu verlieren. 
Anschließend wird auf Grundlage der definierten Operatoren eine Implementierung
entwickelt, welche Effizienz, Korrektheit und Nutzbarkeit zum Ziel hat. Es wird gezeigt, wie intelligente\linebreak
Algorithmen die Laufzeit für das Berechnen der Operationen um ein vielfaches verringern können.
\end{abstract}

\tableofcontents
\listoffigures
\listoftables

\newpage

\chapter{Einleitung}
\section{Fragestellung und Thema der Arbeit}

Im Zuge der stetigen Digitalisierung und der damit verbundenen Sammlung von \linebreak Daten ergeben 
sich vielseitige Anwendungsszenarien. Es entstehen immer mehr Quellen für die Informationsverarbeitung 
und -beschaffung. Leider ist der Vorgang der Informa\-tions\-digitalisierung heute zum großen Teil 
mit manuellem Aufwand verbunden. Jeder Mensch hat eigene Vorstellungen, wie Informationen und Wissen zu 
repräsentieren sind. Schon beim selben zugrundeliegenden Modell der Datenhaltung können starke
Konflikte zwischen zwei Wissensbasen, also jedweder Art von Informationssammlung, entstehen.
Zu diesen zählen Unterschiede in der Modellierung der Domäne, in der Codierung der Daten oder auch der 
verwendeten Terminologie und vieles mehr \cite{HART10}. \\
Topic Maps ist ein semantisches Datenmodell, welches das Ausmaß der Heterogenität einzuschränken versucht. 
Zwei separat entwickelte 
Wissensbasen, die in Topic Maps repräsentiert sind, lassen sich generisch zusammenführen, wobei auch gleich ein 
semantischer Mehrwert entsteht. Das ist bei den meisten Datenmodellen nicht oder nur schwer möglich. \\
Neben der Zusammenführung an sich, ist es auch interessant zu wissen, welche \mbox{Unterschiede} überhaupt in 
den vorliegenden Wissensbasen vorhanden sind und wo Gemeinsamkeiten bestehen. Dies ist das Thema der vorliegenden
Arbeit. Es sollen jene Unterschiede und Gemeinsamkeiten von \textit{Topic Maps} aufgezeigt werden.
Dabei ist zu Unterscheiden, ob es sich um strukturelle oder atomare Unterschiede handelt. Je nach Be\-trach\-tungs\-winkel 
ergeben sich hier möglicherweise unterschiedliche Aussagen zum selben Sachverhalt. Während zwei Datenbasen als 
\textit{Topic Map} strukturell völlig gleich sein können, können sie sich dennoch in gewissen atomaren 
Eigenschaften unterscheiden. Dieser Fakt ist im Zuge der Arbeit genau herauszustellen und zu behandeln, um 
beide Betrachtungsansätze zu unterstützen. Ist ein Modell für das Bestimmen der Unterschiede entwickelt, soll 
anhand einer Umsetzung gezeigt werden, dass eine solche Be\-trach\-tungs\-weise praktisch möglich und einsetzbar ist.

\pagebreak
\section{Ziel der Diplomarbeit}

Das Ziel dieser Arbeit ist es Unterschiede und
Gemeinsamkeiten in \textit{Topic Maps} zu \linebreak finden. Dabei wird genau zu definieren sein, was
Unterschied und Gleichheit im \linebreak Kontext von Topic Maps bedeutet.
Hierzu werden Operatoren definiert werden, welche analog zur Mengentheorie Vereinigung, Schnitt 
und Differenz von \textit{Topic Maps} berechnen \linebreak können. 
Es sollen die Eigenschaften dieser Operatoren erläutert werden und eine \linebreak effiziente Implementierung
erfolgen.\\
Konkret sollen folgende Fragestellungen beantwortet werden:\\

\begin{enumerate}
  \item Was bedeutet strukturelle Gleichheit zweier \textit{Topic Maps}?
  \item Was bedeutet atomare Gleichheit von \textit{Topics}?
  \item In welchem Zusammenhang stehen diese Gleichheitsbegriffe?
  \item Was ist atomare und strukturelle Ungleichheit und wie kann sie erkannt und \linebreak bestimmt werden?
\end{enumerate}
\vspace{1em}
Aufbauend hierauf ist es nun möglich die Unterschiede zweier \textit{Topic Maps} genauer zu betrachten. 
Ist erst ein Modell für die Unterschiede festgelegt, so sollten damit u.a. auch folgende Fragen beantwortet 
werden können:\\
\begin{enumerate}
  \item Was ist strukturelle Differenz?
  \item Welche \textit{Topics} bzw. \textit{Associations} befinden sich ausschließlich in einer der beiden \textit{Topic Maps}?
  \item Welche \textit{Topics} bzw. \textit{Associations} kommen in beiden \textit{Topic Maps} vor?
  \item Welche \textit{Associations} sind betroffen, wenn ein \textit{Topic} gelöscht wurde?
  \item Welche Eigenschaften von \textit{Topics} haben sich geändert?
\end{enumerate}
\vspace{1em}
Nachdem die Beantwortung der gestellten Fragen theoretisch erörtert wurde, wird das 
Framework \texttt{TMDiff} vorgestellt. Es werden die Vorgehensweise der Berechnung und die entsprechenden Algorithmen
erklärt, mit Hilfe derer die spezifizierten Ergebnisse der Operationen für zwei gegebene \textit{Topic Maps} berechnet 
werden. Es wird ein besonderes Augenmerk auf die
Effizienz der entwickelten Algorithmen gelegt, um Skalierbarkeit und somit das Verarbeiten großer \textit{Topic Maps} gewährleisten
zu können.
\pagebreak
\section{Aufbau der Arbeit}
In Kapitel \ref{grundlagen} werden die Grundlagen für die Arbeit gelegt. Es wird erläutert, was genau 
\textit{Topic Maps} sind und wie sie funktionieren, d.h. wie Wissen in Form einer \textit{Topic Map} repräsentiert wird.
Außerdem wird ein Einblick in Arbeiten gegeben, die im Zusammenhang mit der Fragestellung relevant sind. \\
Kapitel \ref{theory} ist der Hauptteil der Arbeit. Es erfolgt eine mathematische Formalisierung der Konstrukte 
des Topic Maps Datenmodells (TMDM). Aufbauend hierauf werden nun die Operatoren
zum Berechnen der Unterschiede und Gemeinsamkeiten von \textit{\mbox{Topic} Maps} definiert. Anschließend wird 
in Kapitel \ref{implementation} das Framework 
\texttt{TMDiff} vorgestellt und die verwendeten Algorithmen erklärt, analysiert und deren Performance anhand
der \mbox{Umsetzung} evaluiert.
Im Schlussteil erfolgt ein 
Ausblick auf eventuelle Anwendungen und Forschungsfragen, welche sich aus der hier geschaffenen Grundlage 
ergeben und eine Zusammenfassung der Arbeit.

\chapter{Grundlagen}\label{grundlagen}

\section{Terminologie}
Im Topic Maps Datenmodell (TMDM) werden viele Begrifflichkeiten eingeführt, welche auch in dieser Arbeit konsequent genutzt 
werden. Fachterme, wie z.B. "`\textit{Occurrence}"'\linebreak könnten auch mit "`Belegstelle"' übersetzt werden. Dies erschwert jedoch nur 
unnütz das Nachschlagen und das Verständnis beim Lesen von Sekundärliteratur. Alle Begriffe, welche in der Arbeit verwendet werden,
sind entweder direkt definiert oder aus dem TMDM entnommen und können dort nachvollzogen werden. \\
Wenn von einem Konstrukt die Rede ist, so ist damit eine Komponente des TMDM gemeint (s. nächster Abschnitt).  Ein Fragment oder auch 
Topic-Fragment ist ein
Tupel. Es besteht aus einer Menge von \textit{Subject Identifiers}, \textit{Subject Locators}, 
\textit{Item Identifiers}, \textit{Names}, \textit{Variants} und \textit{Occurrences}. Ein Topic-Fragment ist eine Repräsentation 
eines \textit{Topics} aus der gegebenen \textit{Topic Map}. \\
Topic Maps-Konstrukte werden zum besseren Verständnis kursiv geschrieben. Topic Maps jedoch nicht, wenn
damit das Datenmodell gemeint ist.
Zu alldem folgen später noch ausführliche Erläuterungen.

\section{Einführung in das Topic Maps Datenmodell}\label{grundlagenTopicMaps}
Die folgenden Ausführungen sind zu großen Teilen an \cite{PEP00} angelehnt, worin Pepper eine gute 
Einführung in das Thema Topic Maps gibt.\\
Es folgt ein Überblick über das TMDM und dessen Konstrukte. Als Konstrukte 
werden alle Komponenten einer \textit{Topic Map} bezeichnet, also 
\textit{Topics}, \textit{Names}, \textit{Variants},\linebreak \textit{Occurrences}, \textit{Associations} und
\textit{Roles} (dazu später mehr) und die \textit{Topic Map} selbst. Außerdem wird der Begriff der Identität erläutert, da dieser eine 
entscheidende Rolle bei der Definition der Operatoren spielt.
\pagebreak

\subsection{Topic Maps}

"`Eine Topic Map ist eine Repräsentation von Informationen, welche benutzt wird, um Informationsobjekte
zu beschreiben und zwischen ihnen zu navigieren."'\cite{NEW01} \mbox{Zentral} ist hierbei das sogenannte 
"`Aussagegegenstandszentrierte Modellierungsparadigma"' \linebreak\cite{MAI08}. Dass heißt, die Informationsobjekte stehen
bei der Modellierung der Wissens\-basis im Zentrum, sie sind sozusagen das "`Herz"' der \textit{Topic Maps} \cite{LMG02}.
Darauf aufbauend werden Beziehungen (\textit{Associations}) zwischen diesen Aussagegegenständen \mbox{(\textit{Topics})} und deren 
Eigenschaften (\textit{Occurrences}) modelliert.
Ausgehend von dieser Modellierung ist es nun möglich von \textit{Topics} über \textit{Associations} zu anderen \textit{Topics}
zu navigieren. \textit{\textbf{T}opics}, \textit{\textbf{A}ssociations} und \textit{\textbf{O}ccurrences}
werden als das "`TAO"' der \textit{Topic Maps} bezeichnet
\cite{PEP00}. Dieses wird im folgenden Abschnitt erklärt. \\
Zusammenfassend kann eine \textit{Topic Map} als selbstverwaltende Wissensbasis bezeichnet werden. Jede Information an sich 
kann als Informationsobjekt interpretiert und somit als \textit{Topic} repräsentiert werden. Die Zusammenhänge, welche 
jene Informations\-objekte verbinden, werden dann durch \textit{Associations} repräsentiert.
Selbstverwaltend ist die Wissens\-basis dadurch, dass Informationen automatisch in den für sie relevanten
Kontext gestellt werden. Die repräsentierte Information hat in ihrem Kontext eine definierte Identität. Dadurch
wird doppelt repräsentiertes Wissen automatisch erkannt und zusammengeführt, wobei etwaige Konflikte aufgelöst werden. 
Topic Maps ist also ein mächtiges Datenmodell, mit dem Wissen strukturiert repräsentiert und abgespeichert werden kann.

\subsection{Das Topic Maps TAO}

\subsubsection{Topics}\label{topicDescr}
Jede Entität, welche durch 
irgendeine Aussage beschrieben wird, kann in einer \textit{Topic Map} als \textit{Topic} repräsentiert werden. Dabei
ist es völlig irrelevant um welches Objekt, Subjekt oder welchen materiellen oder immateriellen 
Gegenstand es sich handelt, so lange nur in irgendeiner Form eine Aussage über die zu betrachtende
Entität getroffen werden kann:
\begin{quote} 
A \textbf{subject} can be anything whatsoever, regardless of whether it exists or has any other specific 
characteristics, about which anything whatsoever may be asserted by any means whatsoever. In particular, 
it is anything about which the creator of a topic map chooses to discourse.  \cite{TMDM} 
\end{quote}
\pagebreak
Ein \textit{Topic} repräsentiert also ein "`Ding"' aus der realen Welt. Außerdem steht das Wort \textit{Topic} auch für ein 
Element in der \textit{Topic Map} (welches eigentlich als Topic Link \linebreak bezeichnet wird) \cite{PEP00}. In dieser Arbeit wird 
für beides das Wort \textit{Topic} genutzt, da sich jeweils aus dem Kontext erschließt, welche Bedeutung 
gemeint ist. \\

\textit{Beispiel} (s. Abb. \ref{topicsWithTypes}) \\

Subjects ("`Dinge"', Entitäten) einer Wissensbasis, die berühmte Naturwissen"-schaftler 
und deren Arbeiten modelliert, könnten z.B.
"`Albert Einstein"', "`Wilhelm Ostwald"', "`Werner Heisenberg"', "`Relativitätstheorie"' und "`Leipzig"' sein. 
Es werden hier also \linebreak Personen, ein Forschungsgebiet und ein Ort repräsentiert. Diese drei Oberbegriffe sind 
gleichzeitig
Kategorien oder Typen der \textit{Topics}, welche die genannten Subjects in einer \textit{Topic Map} repräsentieren.\\
Eine tatsächliche Kategorisierung im Datenmodell erhöht den Grad der Strukturierung. Sie ist in 
Topic Maps durch sogenannte \textit{Topic}-Typen realisiert. Diese Kategorien (oder Typen) sind ebenfalls 
\textit{Topics} und es
wird eine Typ-Instanz-Beziehung zwischen den\linebreak jeweiligen Instanz- und Typ-\textit{Topics} erstellt. (siehe 
Abbildung \ref{topicsWithTypes}). \\ 

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/TopicTypenBeispiel}
  \caption{Beispiel Topics mit entsprechenden Topic-Typen}
  \label{topicsWithTypes}
\end{figure}

\pagebreak

%Genauso wie man Dinge in der realen Welt mit bestimmten Eigenschaften beschreiben würde, ist dies auch 
Eigenschaften, welche mit einem Aussagegegenstand (\textit{Topic} in der \textit{Topic Map}) \linebreak verbunden werden, 
können als \textit{Occurrences} 
(Abschn. \ref{occ}) modelliert werden. Solche Eigenschaften sind z.B. Größe, Geburts- bzw. Sterbeort oder Farbe. 
Eine besondere Eigenschaft eines Aussagegegenstandes ist dessen Name, da dieser als kontextabhängige Referenz für
den Aussagegegenstand genutzt wird. Äquivalent geschieht dies auf Ebene des TMDM. Namen, repräsentiert 
als \textit{Names}, dienen als 
kontextabhängiges "`Label"' \cite{TMDM} des \textit{Topics}. So könnte beispielsweise "`Lipsia"' ebenfalls 
ein \textit{Name} des \textit{Topics}
"`Leipzig"' im Kontext "`historische Namen"' sein. Der \textit{Name} eines \textit{Topics} muss nicht eindeutig in der 
\textit{Topic Map} sein. So könnte auch ein \textit{Topic}, welches für einen Ort in \linebreak Nord-Dakota (New Leipzig) steht, durchaus den 
\textit{Name} "`Leipzig"' haben. Dies wirft die Frage auf, wie \textit{Topics} eindeutig referenziert werden können oder anders formuliert:
Was ist die Identität eines \textit{Topics}? Dies ist eine wichtige Frage, welche ausführlich in Abschnitt \ref{identity1} beantwortet wird.
Der \textit{scope} (s. Def. \ref{defName}) eines \textit{Names} 
definiert den schon ge\-nannten Kontext oder anders gesagt, die Bedingungen, unter 
welchen der vorgestellte \textit{Name} gültig ist. Er erlaubt es, verschiedenste Namen der selben Sache für
unterschiedliche Zwecke frei zu definieren.
Diese können z.B. Spitznamen, Login-Namen, Trivialnamen \linebreak chemischer Verbindungen und vieles mehr sein. \\
\textit{Topics} stellen das Grundgerüst der Modellierung von Informationen und Informations\-objekten
in \textit{Topic Maps} dar. Stehen einzelne Informationsobjekte in unmittelbarem Zusammenhang, so 
lässt sich dieser ebenfalls repräsentieren. Dies geschieht durch \linebreak \textit{Associations}, welche im nächsten 
Abschnitt erläutert werden.

\subsubsection{Associations}

Stehen also zwei (oder mehr) Aussagegegenstände in Beziehung zueinander, so lässt sich dies in Topic Maps mit Hilfe  
von \textit{Associations} repräsentieren. \textit{Associations} verbinden zwei oder mehr \textit{Topics} miteinander 
und haben einen Typ (dieser ist wieder ein \linebreak \textit{To\-pic}), welcher die "`Natur der Beziehung repräsentiert"' \cite{TMDM}.
Jedes Ding, wel\-ches in Beziehung zu anderen Dingen steht, spielt dabei eine ganz bestimmte Rolle. So ist "`Leipzig"' eine 
Stadt in "`Deutschland"', was beide Dinge miteinander verbindet. "`Leipzig"' spielt dabei die Rolle der Stadt
und "`Deutschland"' die Rolle des Landes. Dieser komplexe Zusammenhang wird in Topic Maps durch die Konstrukte 
\textit{Association}, \textit{Role} und \textit{Topic} repräsentiert. \textit{Topics} sind Rollenspieler in 
\textit{Associations}.\\ 

\pagebreak

\textit{Beispiel} (s. Abb. \ref{assocEx})\\

Betrachtet man die Beziehung zwischen "`Leipzig"' und "`Ostwald"', so ist "`Leipzig"' die Wirkungsstätte von "`Ostwald"' und
"`Ostwald"' ist Wissenschaftler in Leipzig. 
In Topic Maps-Terminologie heißt dies: Das \textit{Topic} "`Leipzig"' spielt die \textit{Role} der Stadt und das \textit{Topic}
"`Ostwald"' spielt die \textit{Role} des Wissenschaftlers in der
\textit{Association} Forschungsstätte.  
In Abb. \ref{assocEx} wird dieser Sachverhalt verdeutlicht. \textit{Topics} (hier als Spieler oder Typen) 
werden als Kreise, die \textit{Roles} als 
Dreieck und die \textit{Association} als Viereck dargestellt.

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/AssoziationBeispielLeipzigOstwald}
  \caption{Beispiel für die Repräsentation einer Beziehung durch eine \textit{Association} mit \textit{Roles} und Spielern}
  \label{assocEx}
\end{figure}

\subsubsection{Occurrences}\label{occ}
Wie oben erwähnt, sind \textit{Topics} Stellvertreter für Dinge der realen Welt, welche in einer
\textit{Topic Map} repräsentiert werden sollen. Jedes solches "`Ding"' hat neben Namen, Identität und Beziehungen zu
anderen Dingen auch bestimmte Eigenschaften. Diese Eigenschaften müssen an sich nicht selbst wieder 
ein eigener Aussagegegenstand sein, sondern sind nur an diesen angehängt. Solche Eigenschaften werden in 
Topic Maps mit dem Konstrukt \textit{Occurrence} modelliert.\\

\pagebreak

\textit{Beispiel} (s. Abb. \ref{occEx}) \\

Betrachtet man z.B. Leipzig als \textit{Topic} in einer \textit{Topic Map}, so könnten (je nach \linebreak modellierter Domäne) Fläche oder
Einwohnerzahl relevante Informationen sein. Für genau solche Informationen, welche Eigenschaften eines 
Aussagegegenstandes sind, \linebreak bietet sich eine \textit{Occurrence} als Konstrukt an.\\
\textit{Occurrences} sind immer über die "`Vater-Beziehung"' mit einem \textit{Topic} verbunden und haben u.a. einen Typ, der die
Art der Information und einen Wert, der das eigentliche Datum, das gespeichert werden soll, darstellt. 
Im Beispiel (s. Abb. \ref{occEx}) sind "`Fläche"' und "`Einwohner\-zahl"' die Typen der beiden \textit{Occurrences} und die entsprechenden Werte
sind $297,36$ und $522.883$. Die \textit{Occurrence} mit dem Typ "`Fläche"' hat hier zusätzlich 
noch einen Datentyp (welcher letztendlich eine URI ist, hier aber vereinfacht als $km^2$ dargestellt wird).

\begin{figure}[H]
  \centering
  \includegraphics[height=7cm]{Grafiken/TopicBeispielLeipzigOccurrences}
  \caption{Beispiel für ein \textit{Topic} mit zwei \textit{Occurrences}}
  \label{occEx}
\end{figure}

\pagebreak

\section{Reifikation}\label{reification}
Reifikation ermöglicht es Aussagen über Aussagen zu treffen.
\begin{quote}
 The act of reification is the act of making a topic represent the subject of another topic map construct in the same topic map. 
 For example, crea\-ting a topic that represents the relationship represented by an association is reification. \cite{TMDM}
\end{quote}
Es wird also ein \textit{Topic} erstellt. Dieses \textit{Topic} ist nun Stellvertreter für irgendein anderes \textit{Topic Map}
Konstrukt, beispielsweise eine \textit{Association}. So könnten u.a. zusätzliche \textit{Names} mit mehreren \textit{Variants} mit der 
reifizierten \textit{Association} in Verbindung gebracht werden. \textit{Topics} können nicht reifiziert werden, da sie selbst
schon repräsentiert sind und Aussagen über sie direkt durch das \textit{Topic} an sich gemacht werden können.
Weiterhin ist definiert, dass zwei identische \textit{Topics} A und B nicht unterschiedliche Konstrukte reifizieren dürfen. 
\begin{quote}
It is an error if A and B both have non-null values in their [reified] properties which are different. \cite{TMDM}
\end{quote}
Dies bedeutet, dass zwei \textit{Topics}, die beide identisch nach Definition \ref{eqOfTop} sind, nicht \linebreak unterschiedliche Konstrukte
reifizieren dürfen.
Dieser mögliche Fehler in der Modellierung wird an folgendem Beispiel klar:\\
Gegeben seien zwei \textit{Associations}, die nicht identisch sind. Nun werden 
beide \textit{Associations} von zwei \textit{Topics} reifiziert, welche den 
selben \textit{Subject Identifier} haben. Normalerweise sollten 
die beiden \textit{Topics} von Anfang an zusammengefügt werden, da sie  
identisch sind. Beim Vergleich von zwei unabhängig entstanden \textit{Topic Maps} 
oder etwa beim Hinzu\-fügen eines neuen \textit{Subject Identifiers} zu einem der 
beiden \textit{Topics}, kann dieser Fehler jedoch immer noch auftreten. Diese beiden 
\textit{Topics} stehen nun für ein und dasselbe \linebreak Subject, in diesem Fall sind das 
die \textit{Associations}. Sie repräsentieren ein und 
den selben Aussagegegenstand, sind aber dennoch nicht identisch. \\
Dieser logische Widerspruch kann
nicht aufgelöst werden. Es ist aber herauszuheben, dass dies kein Fehler im Datenmodell an sich ist, sondern
von fehlerhafter (also widersprüchlicher) Modellierung ausgegangen werden kann, sollte dieser Fall auftreten. \linebreak
Deshalb wird in den folgenden Ausführungen davon ausgegangen, dass die beschriebene Konstellation nicht auftritt. 
Sie wird also, wie im TMDM beschrieben, als Fehler \linebreak behandelt.

\section{Topic Maps als Graphen}

Wie in Definition \ref{defTM} festgelegt, ist eine \textit{Topic Map} ein Tupel 
aus einer Menge \textit{Topics} und einer Menge \textit{Associations}. \textit{Associations}
stellen eine Beziehung \linebreak zwischen ihren Spielern her. Diese Struktur erinnert an 
die mathematische Struktur der Hypergraphen \cite{WIKIHYPER}. 
Mehrere Knoten 
können hier über eine Hyperkante miteinander verbunden werden. Die Knoten sind dabei
die \textit{Topics} und die Hyperkanten sind die \textit{Associations}, welche eine Menge
von \textit{Topics} mit\-einander verbindet. Unter diesen Voraussetzungen lassen sich 
\textit{Topic Maps} in Graphen transformieren. Die Rück\-transformation gelingt nicht, 
da bei der Transformation der \textit{Topic Map} in den Graphen sehr viele \linebreak Informationen 
verloren gehen (\textit{Roles}, \textit{scopes}, \textit{Typen}, ...). \\
Alle Darstellungen von \textit{Topic Maps} als Graphen, auch in dieser Arbeit, dienen \linebreak ausschließlich 
zur Veranschaulichung eines Sachverhaltes,
entbehren jedoch jeglicher \linebreak Standardisierung. Darum werden hier die Betrachtungen auf die spezifizierten Mengen \linebreak
beschränkt und 
sich bekannter Sachverhalte aus der Mengentheorie bedient.
So gibt es bereits Möglichkeiten Unterschiede und Gemeinsamkeiten zweier Mengen zu \linebreak bestimmen (s. Abschn. \ref{introductionSetTheory}).
Voraussetzung dafür ist, dass die Elemente der \linebreak Mengen eindeutig bestimmbar sind (z.B. das Element "`2"' in der Menge der natürlichen
Zahlen). Diese Voraussetzung ist für Topic Maps erfüllt, da jedes Element eine eindeutige \linebreak Identität besitzt. (s. Abschn. \ref{constAndId})\\
An dieser Stelle sei erwähnt, dass die Darstellung von \textit{Topic Maps} in graphischer Form durchaus praktischen Nutzen hat. Kleine 
\textit{Topic Maps} können so leicht veranschaulicht werden, jedoch hilft eine Transformation 
an dieser Stelle nicht die anfängliche Problemstellung zu vereinfachen. Es wäre zusätzlicher Aufwand nötig, eine \textit{Topic Map}
in eine Graphenstruktur zu transformieren, was die Arbeit eher erschwert.

\section{Gleichheit und Identität}\label{identity1}
Ob zwei Dinge gleich oder gar dasselbe sind, lässt sich allgemeingültig nur äußerst schwer beantworten. Mit dieser Frage 
beschäftigten sich schon viele Philosophen und Mathematiker (u.a. Hobbes \cite{HOBBES}, Leibnitz \cite{LEIBNITZ}, siehe auch \cite{SEIFARTH}). 
Leibnitz argumentiert, dass sich zwei Körper gleichen, wenn kein Unterschied zwischen ihnen besteht \cite{LEIBNITZ}.
Betrachtet man zwei nebeneinander liegende Körper, ist so Gleichheit oder Ungleichheit nachweisbar. Jedoch birgt die Leibnitz'sche
Definition ein Problem in sich.
Was ist, wenn sich Eigenschaften eines Körpers
über die Zeit hinweg ändern oder wenn sie für die Betrachtung irrelevant sind? Beispielsweise ist es u.U. (abhängig von der 
modellierten Domäne) egal, welche Farbe ein Lieferwagen hat. Es sind für einen Routenplaner also alle gleich großen 
Lieferwagen identisch. Der Fahrer des Wagens muss jedoch wissen, welchen Wagen er zum Zielort zu fahren hat.
Hobbes erkennt folgendermaßen:
\begin{quote}
Wenn die Identität eines Gegenstandes in Frage steht, ist vielmehr der Name entscheidend, 
der ihm gegeben wurde. Es ist etwas anderes, zu fragen, ob Sokrates derselbe Mensch, 
und etwas anderes, ob er derselbe Körper bleibe; denn sein Körper kann als Greis nicht 
derselbe sein, wie er es als Kind war, schon der Größenunterschiede wegen. \cite{HOBBES}
\end{quote}
Welches grundsätzliche Problem der Definition der Identität über den Namen existiert, wurde bereits in Abschn. \ref{topicDescr}
diskutiert. \\
Lässt sich die Identität einer Entität eindeutig bestimmen, so sind nur diejenigen \linebreak Entitäten \textit{gleich}, welche dieselbe
Identität besitzen. In diesem Sinne unterliegt die \mbox{Bedeutung} des Begriffes Identität und die damit einhergehende Bedeutung
der \textit{\mbox{Gleichheit}} immer der Interpretation des Modellierers der Domäne. Zumindest
kann nicht davon ausgegangen werden, dass sich ein Modellierer an eine festgelegte Definition hält. Deshalb sollte die Idee \textit{Gleichheit}
im Datenmodell so flexibel wie möglich umgesetzt werden.\\
Zwei \textit{Topics} sind gleich, wenn sie dieselbe Identität besitzen. In diesem Sinne
unterstützt das TMDM dabei jedwede Definition von \textit{Gleichheit}, da der jeweilige
Entwickler die Identität jedes \textit{Topics} frei definieren kann. Dies erfolgt durch das Zuweisen eines Uniform Resource Identifier (URI) zu dem
entsprechenden \textit{Topic}.
\begin{quote}
Ein Uniform Resource Identifier [...] ist ein Identifikator 
und besteht aus einer Zeichenfolge, die zur Identifizierung einer abstrakten oder physischen Ressource dient. URIs werden zur Bezeichnung von 
Ressourcen (wie Webseiten,[...]) im Internet und dort vor allem im WWW eingesetzt. \cite{WIKIURI} 
\end{quote}
Die Idee dahinter ist, dass die URI auf eine Quelle im Internet verweist, welche Informationen über den beschriebenen Aussagegegenstand 
enthält. Dies ist aber nicht zwingend notwendig. Es existieren auch mehrere fachspezifische \cite{BIOTAXONOMIE} oder allgemeine Verzeichnisse
\cite{SUBJ3CT}, welche URIs für Dinge bereithalten. \\
Um einem \textit{Topic} eine Identität zuzuweisen, die über eine URI definiert ist, gibt es die Menge der \textit{Subject Identifier},
welche jedem \textit{Topic} zugehörig ist.  Wird die URI zu dieser Menge hinzugefügt, so ist die Identität des \textit{Topics} 
festgelegt (mehr dazu in Abschn. \ref{defTopic}). \\
Ein kleines Problem ergibt sich, wenn versucht wird das Dokument an sich, welches sich hinter der URI verbirgt, zu repräsentieren. 
Soll beispielsweise das Datum der Erstellung eines Wikipedia Artikels in der Wissensbasis abgebildet werden, so kann für das \linebreak
\textit{Topic}, welches den Wikipedia Artikel repräsentiert, nicht die URL des Artikels als \textit{Subject Identifier} benutzt werden. Dies 
liegt an der im TMDM definierten Semantik der \textit{Subject Identifier}. Die Ressource, welche durch den \textit{Subject Identifier} referenziert ist,
soll das Topic beschreiben und nicht das Topic selbst sein. Das Erstellungsdatum würde sich in diesem Fall also auf die Entität beziehen,
welche durch den Wikipedia \mbox{Artikel} beschrieben ist und nicht auf den Artikel an sich.
Abhilfe für dieses Problem
schafft das TMDM durch die Menge der \textit{Subject Locator}, welche mit dem \textit{Topic} \mbox{assoziiert}
ist. Wird eine URI dieser Menge hinzugefügt, so 
repräsentiert das \textit{Topic} das Dokument an sich und nicht das Ding, welches durch das Dokument beschrieben wird. \\
Das TMDM liefert also eine Möglichkeit, jede Entität unabhängig von deren Eigenschaften abzubilden 
und deren Identität frei zu definieren. Konkret ist dadurch \mbox{eine} Trennung der Identität und Eigenschaften der Entität erfolgt.
Diese Trennung erlaubt es nun strukturelle Zusammenhänge in der Wissensbasis unabhängig von 
einzelnen Eigenschaften der modellierten Entitäten zu untersuchen. Genauso können Unterschiede in den Eigenschaften bestimmt werden, 
ohne dabei die strukturellen Zusammenhänge  \linebreak betrachten zu müssen. All dies wird später genauer erläutert und erklärt werden.

\section{Vergleich von RDF und Topic Maps}\label{compRDFandTM}
Topic Maps haben den Zweck, Wissen semantisch zu repräsentieren. Einen ähnlichen Ansatz zur Wissensrepräsentation 
ist das RDF-Datenmodell. Es soll hier keine ausführliche Einführung in dieses Datenmodell gegeben werden, da dies
den Umfang der Arbeit übersteigt. Einen Einstieg in RDF bietet beispielsweise \cite{VERTAN} oder \cite{MILLER98}.
Ein kurzer Vergleich zwischen den beiden Repräsentationsparadigmen bietet sich an, da viele Arbeiten im 
Bereich von RDF Denkansätze für die Lösung des vorliegenden Problems bieten.

\subsection{Modellierung}
In \cite{GAR04} findet sich eine ausführliche Beschreibung der konzeptionellen und spezifischen Gemeinsamkeiten und Unterschiede von 
RDF und Topic Maps. Die folgenden Ausführungen sind zum Teil von dort entnommen. Beide Datenmodelle haben "`Dinge"' als zentrale 
Aussagegegenstände. Diese "`Dinge"' werden über "`Symbole"' in der jeweiligen Wissensbasis repräsentiert.
\pagebreak
\begin{quote}
RDF and topic maps are both identity-based technologies. That is, the key concept in both is
"`symbols"' representing identifiable "`things"', which statements can be made about. \cite{GAR04}
\end{quote}
Die genannten Symbole sind in RDF die RDF-Nodes (sie repräsentieren sogenannte Ressources) und in Topic Maps die 
\textit{Topics} (sie repräsentieren sogenannte Subjects). Ressources und Subjects sind im Prinzip das Gleiche, 
nämlich ein Gegenstand, welcher modelliert werden soll.
RDF erlaubt es nun sogenannte Statements über die jeweiligen Ressources zu erstellen. 
Statements setzen den Gegenstand der Betrachtung
in einen Kontext, sind Träger von Information und Semantik. Sie bestehen aus der Ressource an sich, einer Property 
und einer zweiten Ressource bzw. einem Literal. Miller beschreibt das RDF-Datenmodell wie folgt:
\begin{quote}
Resources have properties (attributes or characteristics). RDF defines a \linebreak resource as any 
object that is uniquely identifiable by a Uniform Resource Identifier (URI). The properties associated with resources are 
identified by property types, and property types have corresponding values. Property types express the relationships of values associated 
with resources. In RDF, values may be atomic in nature (text strings, numbers, etc.) or other \linebreak resources, which in turn may have their own 
properties. \cite{MILLER98}
\end{quote}
Prinzipiell ähnelt dies dem TMDM. Wichtige Unterschiede sind, dass im TMDM \mbox{Namen} gesondert behandelt werden
(in RDF sind sie ein Statement) und dass \textit{Occurrences} mächtigere Konstrukte sind, als einfache RDF-Statements mit atomaren Werten. Sie haben
einen Typ, einen Scope, einen Datentyp (Abschn. \ref{defOccurrence}) und können direkt reifiziert (s. Seite \pageref{reification}) werden. 
RDF-Statements mit einer Ressource im Wert, können mit 
\textit{Associations} in Topic Maps verglichen werden. In beiden Fällen werden zwei 
Ressources bzw. Subjects in Beziehung gesetzt. Beziehungen in RDF
sind jedoch unidirektional und rollen\-frei. Trotz der hier genannten Unterschiede ist es möglich, Topic Maps in RDF zu konvertieren und
umgekehrt \cite{GAR04, GAR08}. Ein wesentlicher Teilaspekt dieser \linebreak Konvertierung ist die Feststellung der Identität einzelner Konstrukte.

\subsection{Identität}
Wie die Identität eines \textit{Topics} definiert ist, wurde schon in Abschnitt \ref{identity1} erörtert. RDF unterscheidet drei 
verschiedene Typen von Nodes, nämlich Literal Nodes, URI Nodes und blank Nodes. Ein Literal Node besteht 
aus einer atomaren Zeichenkette, welche auch dessen Identität definiert. Haben zwei URI Nodes dieselbe URI 
als Label, so werden sie als identisch angesehen. Hierbei gibt es keine Unterscheidung zwischen dem Referenzieren 
von Ressourcen an sich oder der Objekte, welche durch die Ressource beschrieben werden. Die Identität von blank 
Nodes ist nur über Statements feststellbar, in denen sie verwendet werden. Auch hier ist prinzipiell ein 
Mapping auf Konstrukte im TMDM möglich, jedoch aufwändiger \cite{GAR04}.\\
Im folgenden Abschnitt wird noch einmal auf die Erfahrungen eingegangen, die beim Berechnen von Unterschieden in RDF gemacht wurden, um eine 
effiziente und prak\-tische Methodik für Topic Maps zu entwickeln.

\section{Bisherige Arbeiten}\label{relatedWork}
\subsection{Methoden der Spezifikation von Unterschieden}
Klein definiert eine Ontologie als "`a specification of a conceptualization"' \cite{KLE02}. Auf Grundlage dieser Definition
sind \textit{Topic Maps} Ontologien. Eine zugrundeliegende Konzeptualisierung einer Domäne lässt sich mit Hilfe des
TMDM einfach spezifizieren. Es existieren bereits einige Arbeiten zum Vergleich von 
Ontologien, welche mit Hilfe von RDF spezifiziert wurden \cite{KLE02, COA10, NOY04}. Auch wenn zwischen
RDF und Topic Maps konzeptionelle Unterschiede bestehen (s. Abschn. \ref{compRDFandTM}), bietet sich ein Blick auf die 
bisherigen Erfahrungen mit diesen Technologien an.
So erläutert Klein, wie Verände\-rungen in Ontologien 
angegeben werden können. Er nennt drei grundsätzliche Ansätze:

\begin{enumerate}
 \item Liste mit Änderungsoperationen ("`transformation specification"')
 \item Liste mit Mappings ("`mapping"')
 \item Liste mit (TMDM-)Konstrukten ("`replacement"')
\end{enumerate}

Die erste Methode ist das Angeben einer Liste mit Änderungsoperationen, welche \textit{Topic Map} $A$
in \textit{Topic Map} $B$ überführen. Für Topic Maps gibt es bereits mehrere Anfragesprachen (TMQL \cite{BAR07}, tolog \cite{GAR06}), die 
für dieses Verfahren in Frage kämen. So könnte das Fehlen eines Konstruktes in einer der \textit{Topic Maps}, über 
ein Update-Statement in einer der Anfragesprachen symbolisiert werden. Die auf diese Art und Weise bestimmte Liste von Änderungsoperationen 
für jedes einzelne, fehlende bzw. zusätzliche Konstrukt könnte nun direkt angewendet werden, um $A$ in $B$ 
zu überführen. Jedoch verliert man durch das bloße Angeben von Änderungstransformationen 
strukturelle Zusammenhänge. So zieht das Löschen eines Topics 
auch das Löschen der entsprechenden \textit{Association} nach sich, in denen es Spieler 
ist (man beachte die Definition der Identität von \textit{Association} in 
Kapitel \ref{constAndId}).

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/LoeschenEinesTopicsInAssoziation}
  \caption{Löschen des \textit{Topics} x zieht das Löschen der \textit{Associations}, in welchen es mitspielt, nach 
  sich, da die \textit{Association} ihre Identität verliert}
  \label{deletTopicInAssoc}
\end{figure}
TMQL bietet zwei mögliche Formen des Updates für solch eine Situation. Das Löschen der \textit{Association} kann 
%http://www.slideshare.net/LEler/tmql-session7
durch Kaskadierung forciert werden oder nicht erfolgen \cite{TMQLSLIDES}. Beide Möglichkeiten liefern kein 
befriedigendes Ergebnis. 
Wird kaskadiert, ist die \linebreak Wissensbasis in einem konsistenten Zustand. Das Fehlen der \textit{Association} ist jedoch
nicht direkt erkennbar, sondern nur über Betrachtung aller Update-Statements und der ursprünglichen
\textit{Topic Map} rekonstruierbar. Wird beim Löschen des \textit{Topics} nicht kaskadiert, so bleibt eine 
\textit{Role} ohne den entsprechenden Player zurück. Die \textit{Topic Map} ist an dieser Stelle nicht mehr 
konsistent mit dem TMDM. Des Weiteren ist es so nicht einfach möglich, Gemeinsamkeiten in den beiden 
\textit{Topic Maps} anzugeben, da tatsächlich nur Unterschiede in einer
Änderungsoperation reflektiert werden. Eine Erweiterung des Konzeptes der Änderungsoperationen 
(bspw. eine \textit{keep}-Operation) würde dieses Pro\-blem lösen. Diese sind jedoch in den Query 
Standards (TMQL, tolog) nicht standardisiert oder vorgesehen.\\
Die zweite Möglichkeit ist, ein Mapping zwischen den unterschiedlichen \textit{Topic Maps}
anzugeben, welches gleiche Konstrukte miteinander verbindet und somit Gemeinsam\-keiten und 
Unterschiede, anhand des Vorhandenseins bzw. Nicht-Vorhandenseins von Mappings identifiziert. 
Der Nachteil dieser Methode ist die zusätzlich benötigte Datenstruktur. Dies ist, wie die letzte 
Methode zeigt, nicht zwingend nötig und erfordert abermals eine Interpretation. Das Ergebnis muss anhand
beider \textit{Topic Maps} und des Mappings betrachtet werden, um die eingangs gestellten Fragen beantworten zu können.\\
Die letzte Methode, das explizite Angeben der Elemente, welche gemeinsam oder nicht gemeinsam in den jeweiligen \textit{Topic
Maps} auftreten, bietet sich als beste Lösung an, da die komplette Strukturinformation der 
Unterschiede und Gemeinsamkeiten beider \linebreak \textit{Topic Maps} erhalten bleibt. Es werden keine Zusatztechniken, wie
Transformations\-sprachen (TMQL) oder eine Mappingstruktur benötigt. Außerdem ermöglicht das \linebreak Merging-Modell von Topic Maps ein 
einfaches \textit{Zusammenführen} von \textit{Topic Maps}. \mbox{Zusätzlich} soll noch die \textit{Differenz} und der \textit{Vergleich} ermöglicht 
werden.
%Überführen von Topic Map $A$ und der entsprechenden Unterschiede (hier als Topic Map) in Topic Map $B$. 
Eine genaue Spezi\-fikation und Beschreibung dieser Methoden findet in den folgenden Kapiteln statt.

\subsection{Der Wandora Ansatz}
Mit dem Wandora-Projekt \cite{WANDORA} existiert bereits eine Implementierung, welche \mbox{Unterschiede} zwischen zwei
\textit{Topic Maps} berechnet. Die dort verwendete Methode zur Spezifikation der \mbox{Unterschiede} ist die 
erstgenannte der zuvor erwähnten Methoden. \mbox{Unterschiede} werden als Menge von Änderungen 
angegeben. Es existieren zwei nicht weiter spezifizierte Formate: \textit{HTML} und \textit{Patch}.\\
Wird das Format \textit{HTML} gewählt, so ist das Ergebnis im Wesentlichen eine Liste von "`Deleted"', "`Changed"' und "`Added"' 
Anweisungen, welche \textit{Topic Map} $A$ in \textit{Topic Map} $B$ überführt (Überführung wird hier nicht ausgeführt). Abgesehen
von der eben schon erläuterten Kritik an dieser Methode fehlt hier zusätzlich eine formale Beschreibung des Formates.
Eine Liste von TMQL-Statements wäre z.B. benutzbarer und frei von \mbox{jeglicher} Fehlinterpretation des Nutzers. Beispielsweise ist nicht 
klar, ob bei einer "`Deleted"'-Anweisung kaskadiert werden soll oder nicht.\\
Wird das Format \textit{Patch} gewählt, wird eine Textdatei erstellt, welche Informationen \mbox{enthält}, die \textit{Topic Map} $A$ intern
in \textit{Topic Map} $B$ transformieren kann. Diese Transformation kann auch rückgängig gemacht werden. Auch hier fehlen Informationen
und Standar\-disierung, um das Tool praktisch nutzbar zu machen.\\
Außerdem tritt auch hier wieder das inhärente Problem auf, Gemeinsamkeiten nicht \mbox{einfach} erkennen zu können. Alles in allem
fehlt es dem Wandora-Tool an einer definierten Spezifikation und Dokumentation. Es ist nicht modular (keine beschriebenen Interfaces 
vorhanden) aufgebaut und somit leider kaum nutzbar.

\subsection{Syntaxbasierter Vergleich}
An dieser Stelle sei auch noch ein Wort zu dateibasierten Diff-Tools, wie z.B. UNIX diff gesagt. In \cite{KLE02, COA10} sind
die jeweils entwickelten Tools am UNIX diff orientiert. Um jedoch einen umfangreichen, strukturellen Vergleich zu erreichen,
werden in \cite{KLE02} Heuristiken hinzugezogen, welche die Semantik der Unterschiede \textquotedblleft erraten\textquotedblright \ 
sollen. Die letzte Entscheidung, ob zwei Konzepte identisch sind, wird hier dem Nutzer überlassen. 
In \cite{COA10} wird eine komplexe Erweiterung der Serialisierung durchgeführt, um
die semantischen Implikationen der Änderung zu verstehen.\\
Die Berechnung von dateibasierten Unterschieden ist per se nicht semantisch. Schon die Frage: "`Ist \textit{Topic} $t$ in 
beiden \textit{Topic Maps}
enthalten?"', kann durch ein dateibasiertes diff nicht befriedigend beantwortet werden. Beispielsweise impliziert das Wegfallen
\mbox{eines} \mbox{Namens} des \textit{Topics} in der zweiten \textit{Topic Map} keinen strukturellen Unterschied, solange sie nach Datenmodell äquivalent
sind. Diesen Unterschied kann ein dateibasiertes \mbox{diff-Tool} nur schwer erkennen und die Komplexität einer solchen 
Implementierung würde die eines Datenmodell-basierten Diffs, wie hier vorgestellt, schnell übersteigen.

\chapter{Theorie}\label{theory}
\section{Formalisierung und Identität}\label{identity2}
In diesem Abschnitt soll erläutert werden, wie eine \textit{Topic Map} formal repräsentiert \mbox{werden} kann. Auf Grundlage dieser 
Repräsentation werden später Operatoren definiert, mit Hilfe derer Unterschiede zwischen \textit{Topic Maps} bestimmt werden 
können. Die Definition der hier genannten Konstrukte sind stark an den Spezifikationen des TMDM \cite{TMDM} 
angelehnt, worin sich auch noch weitere Informationen und Beschreibungen finden. \\
Die in Abschnitt \ref{identity1} diskutierte Interpretation von Identität und Gleichheit gibt einen 
Einblick in die Komplexität der Begriffe im Bezug auf reale "`Dinge"'. Diese "`Dinge"' \mbox{werden} nun als Konstrukte
in der \textit{Topic Map} repräsentiert. In diesem Kapitel geht
es nun ausschließlich um die im TMDM definierte Identität der jeweiligen Konstrukte und nicht die der "`Dinge"'. \\
Es ist für jedes hier definierte Konstrukt eine Menge von Attributen angegeben, welche die Identität des Konstrukts
definieren. Dass heißt, sollten zwei Konstrukte 
in den angegebenen Attributen übereinstimmen, so sind sie identisch. Das TMDM spezifiziert also konkret, was Identität 
der jeweiligen Konstrukte bedeutet. 
Es stehen auch hier, gerade im Anwendungskontext, frei wählbare Definitionen der Identität zur Debatte. 
So kritisiert Vatant, 
\begin{quote}
dass bei Topic Maps [...] die Identität zweier subjects(sic) auf sehr \linebreak eingeschränkte Weise 
ermittelt wird. Er schlägt vor, statt eines einzigen \linebreak identifiers(sic) (einer URI-Zeichenkette) allgemeiner identische 
Werte für eine bestimmte Untermenge der Eigenschaften zu verwenden [...]. \cite{SIG04}
\end{quote}
Diese Diskussion geht jedoch an der Zielsetzung der Arbeit vorbei und wird deshalb nicht weiter fortgeführt. Wie schon genannt, 
soll das TMDM und dessen Definition der Identiät als Grundlage der Arbeit dienen. 
\pagebreak

\subsection{Topic Map Konstrukte}\label{constAndId}

Die jeweiligen Konstrukte sind Tupel, deren Elemente angegeben werden. Es folgt die Angabe der Gleichheitsattribute. Diese 
definieren die Identität der Instanzen des jeweiligen Konstruktes. 
Stimmen die Attribute zweier Konstruktinstanzen überein, so sind sie identisch.\\
Im Anschluss an die Definition wird jeweils eine kurze Beschreibung der Konstrukte angegeben. Es wird 
beispielhaft erläutert, was mit Hilfe des definierten Konstruktes modellierbar ist.

\marktopleft{a}
\begin{definition}[Variant]\label{defVar}
Ein \textit{Variant} $v$ sei ein 5-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $value$ - der Wert des \textit{Variants} als Zeichenkette, 
 \item $scope$ - Menge von \textit{Topics}, welche den Kontext des \textit{Variants} definiert, 
 \item $reifier$ - ein \textit{Topic}, welches der Reifier des \textit{Variants} oder Null ist,
 \item $datatype$ - eine Zeichenkette, welche den Datentyp des \textit{Variants} spezifiziert,
 \item $parent$ - der \textit{Name}, zu welchem der \textit{Variant} gehört.
\end{itemize}
Also: $v = (value, type, scope, reifier, datatype, parent)$\\
Gleichheitsattribute: $value, type, scope, datatype, parent$
\end{definition}\markbottomright{a}

Ein \textit{Variant} ist eine Alternative eines gegebenen \textit{Name}. Der 
\textit{Name} ist zwar im Allgemeinen zu bevorzugen, jedoch kann über den $scope$ ein Kontext definiert werden, in dem
der genannte \textit{Variant} vorzuziehen ist. Ein Beispiel hierfür wäre der \textit{Name} für ein \textit{Topic}, 
welches das Land Deutschland repräsentiert. Hat das \textit{Topic} den \textit{Name} 
\textquotedblleft Germany\textquotedblright, so könnte der $value$ eines \textit{Variants} im $scope$ $\{$
\textquotedblleft deutsch\textquotedblright \ $\}$ \ \textquotedblleft Deutschland\textquotedblright \ sein.

\marktopleft{a}
\begin{definition}[Name]\label{defName}
Ein \textit{Name} $n$ sei ein 6-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $value$ - der Wert des \textit{Name} als Zeichenkette, 
 \item $type$ - ein \textit{Topic}, welches den Typ des \textit{Name} definiert,
 \item $scope$ - Menge von \textit{Topics}, welche den Kontext des \textit{Name} definiert, 
 \item $variants$ - Menge von \textit{Variants} des \textit{Name},
 \item $reifier$ - ein \textit{Topic}, welches der \textit{Reifier} des \textit{Name} oder Null ist,
 \item $parent$ - das \textit{Topic}, zu welchem der \textit{Name} gehört.
\end{itemize}
Also: $n = (value, type, scope, parent, variants, reifier)$\\
Gleichheitsattribute: $value, type, scope, parent$
\end{definition}\markbottomright{a} 

Ein \textit{Name} ist ein Bezeichner für ein \textit{Topic}. Dieser muss nicht eindeutig sein, sollte aber so gewählt sein,
dass man ihn zur Anzeige oder für den Diskurs verwenden kann. Die Verwendung des \textit{Name} wurde schon in 
Kapitel \ref{grundlagen} erläutert. 

\marktopleft{a} \begin{definition}[Role]
Eine \textit{Role} $r$ sei ein 4-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $type$ - ein \textit{Topic}, welches den Typ der \textit{Role} definiert, 
 \item $player$ - das \textit{Topic}, welches der Spieler der \textit{Role} in der $parent$-\textit{Association} ist, 
 \item $parent$ - die \textit{Association}, zu welcher die \textit{Role} gehört, 
 \item $reifier$ - ein \textit{Topic}, welches der \textit{Reifier} der \textit{Role} oder Null ist.
\end{itemize}
Also: $r = (type, player, parent, reifier)$\\
Gleichheitsattribute: $player, type, parent$
\end{definition}\markbottomright{a}

Jede \textit{Association} stellt eine Beziehung zwischen einer Menge von \textit{Topics} her. Diese \textit{Topics} sind 
dann nicht ohne weiteres Teil der \textit{Association}, sondern sie "`spielen eine Rolle"'. Beispielsweise stehen 
"`Vater"' und "`Sohn"' in Beziehung zueinander. Diese Beziehung wird in Topic Maps über eine \textit{Association} 
repräsentiert. Nun spielt hier der "`Sohn"' die Rolle des Kindes und der "`Vater"' die Rolle des Elternteils.
Der Typ der entsprechenden \textit{Role} ist jeweils ein \textit{Topic} "`Kind"' bzw. "`Elternteil"'.

\marktopleft{a} \begin{definition}[Occurrence]\label{defOccurrence}
Eine \textit{Occurrence} $o$ sei ein 6-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $value$ - der Wert der \textit{Occurrence}, 
 \item $type$ - das \textit{Topic}, welches den Typ der \textit{Occurrence} definiert, 
 \item $datatype$ - eine Zeichenkette, welche den Datentyp der \textit{Occurrence} spezifiziert,
 \item $scope$ - Menge von \textit{Topics}, welche den Kontext der \textit{Occurrence} definiert, 
 \item $parent$ - das \textit{Topic}, zu welchem die \textit{Occurrence} gehört, 
 \item $reifier$ - ein \textit{Topic}, welches der \textit{Reifier} der \textit{Occurrence} oder Null ist.
\end{itemize}
Also: $o = (value, type, datatype, scope, parent, reifier)$\\
Gleichheitsattribute: $value, type, datatype, scope, parent$
\end{definition}\markbottomright{a}

\textit{Occurrences} wurden ausführlich in Kapitel \ref{grundlagen} beschrieben.
\pagebreak

\marktopleft{a} \begin{definition}[Association]\label{defAssoc}
Eine \textit{Association} $a$ sei ein 4-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $type$ - ein \textit{Topic}, welches den Typ der \textit{Association} definiert, 
 \item $scope$ - Menge von \textit{Topics}, welche den Kontext der \textit{Association} definiert
 \item $roles$ - nicht leere Menge von \textit{Topics}, welche die \textit{Roles} der \textit{Association} darstellen 
 \item $reifier$ - ein \textit{Topic}, welches der \textit{Reifier} der \textit{Association} oder Null ist.
\end{itemize}
Also: $a = (type, scope, roles, reifier)$\\
Gleichheitsattribute: $role, type, scope$
\end{definition}\markbottomright{a}

An dieser Stelle ist zu bemerken, dass die Identität der \textit{Association} insbesondere von den \textit{Roles} abhängt, deren
Identität wiederum durch deren Player bestimmt ist. Betrachtet man also die Identität von \textit{Associations}, so muss
diese immer als \textquotedblleft Ganzes\textquotedblright \ (mit \textit{Roles} und Playern) betrachtet werden. 
Sollten sich zwei \textit{Associations} nur um eine 
\textit{Role} mit einem entsprechenden
Player unterscheiden, so sind diese voneinander verschieden, auch wenn alle anderen Eigenschaften übereinstimmen.

\marktopleft{a} \begin{definition}[Topic]\label{defTopic}
Ein \textit{Topic} $t$ sei ein 7-Tupel, bestehend aus folgenden Elementen:
\begin{itemize}
 \item $SI$ - (\textit{Subject Identifiers}) eine Menge von Zeichenketten, welche jeweils ein Identifikator des \textit{Topics} ist, 
 \item $SL$ - (\textit{Subject Locators}) eine Menge von Zeichenketten, welche jeweils auf eine Informationsressource zeigen, für die das \textit{Topic} steht, 
 \item $II$ - (\textit{Item Identifiers}) eine Menge von Zeichenketten, welche jeweils ein (interner) Identifikator des \textit{Topics} ist, 
 \item $N$ - eine Menge von \textit{Names} des \textit{Topics},
 \item $V$ - eine Menge von \textit{Variants} des \textit{Topics}
 \item $O$ - eine Menge von \textit{Occurrences} des \textit{Topics},
 \item $r$ - das Konstrukt, welches durch das \textit{Topic} reifiziert wird oder Null.
\end{itemize}
Also: $t = (SI, SL, II, N, V, O, r)$
\end{definition}\markbottomright{a}

\textit{Topics} wurden ausführlich in Abschn. \ref{topicDescr} besprochen. Anzumerken ist, dass die
\textit{Variants} der \textit{Names} vom betrachteten \textit{Topic} Teil der Konstruktdefinition sind, 
da dadurch später die Definition der Operatoren 
vereinfacht wird. Dabei können keine Probleme mit der Identität der \textit{Variants} auftreten, weil der \textit{Name} 
als solches ein Gleichheitsattribut des \textit{Variants} ist (s. Def. \ref{defVar}).\\

Die Gleichheitsdefinition der \textit{Topics} unterscheidet sich ein wenig von der, anderer \mbox{Konstrukte}. \textit{Topics} stellen das zentrale 
Modellierungsgrundgerüst von Topic Maps dar. Sie repräsentieren "`Dinge"', über die Aussagen getroffen werden sollen.
Deshalb ist die De\-finition der Identität der \textit{Topics} von zentraler Bedeutung.

\marktopleft{a} \begin{definition}[Gleichheit von Topics]\label{eqOfTop}
Zwei \textit{Topics} sind identisch, wenn sie in
\begin{itemize}
 \item einer Zeichenkette der \textit{Subject Identifier} oder
 \item einer Zeichenkette der \textit{Subject Locator} oder
 \item einer Zeichenkette der \textit{Item Identifier} oder
 \item einer Zeichenkette der \textit{Subject Identifier} des einen und einer Zeichenkette der \textit{Item Identifier} des anderen \textit{Topics} übereinstimmen oder
 \item das Reified Attribut ein identisches Konstrukt aufweist. 
\end{itemize}
\end{definition}\markbottomright{a}

Schlussendlich ist eine \textit{Topic Map} dann eine Art Container, welcher alle modellierten Informationen beinhaltet:

\marktopleft{a} \begin{definition}[Topic Map]\label{defTM}
Eine \textit{Topic Map} $m = (T,A)$ sei ein Tupel aus einer Menge von \textit{Topics} $T$\\ und \textit{Associations} $A$,
wobei $T = \{t_1, t_2, ..., t_n\}$ und $A = \{a_1, a_2, ..., a_m\}$
\end{definition}\markbottomright{a}

\pagebreak

\section{Operatoren}\label{operators}

\subsection{Einführung in die Mengentheorie}\label{introductionSetTheory}

Definition \ref{defTM} besagt, dass eine \textit{Topic Map} ein Tupel zweier Mengen 
(\textit{Topics} und \textit{Associations}) ist. Das Problem 
Unterschiede in \textit{Topic Maps} zu erkennen, kann (später genauer erläutert) 
auf das Problem reduziert werden, Unterschiede in diesen gegebenen Mengen zu finden.
Deshalb werden im Folgenden die Grundlagen der Mengentheorie und deren Operatoren dargestellt.

\marktopleft{a} \begin{definition}[Menge (nach Cantor)\cite{CANTOR}]
Unter einer „Menge“ verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer
Anschauung oder unseres Denkens (welche die „Elemente“ von M genannt werden) zu einem Ganzen.
\end{definition}\markbottomright{a}

Hier wird die Wichtigkeit der im vorigen Abschnitt vorgestellten Definitionen der Gleichheit von \textit{Topics}
(Def. \ref{eqOfTop}) deutlich.
Sollten Objekte nicht unterscheidbar sein, so können sie nicht als verschiedene Objekte betrachtet werden. 
Identität liefert also Wohlunterscheidbarkeit der Konstruktinstanzen und damit die Möglichkeit Mengenbetrachtungen
für Topic Maps anzustellen.\\\\
Die im Folgenden definierten Operatoren arbeiten auf Mengen. Das Ergebnis der \linebreak Operationen enthält Elemente,
deren Zugehörigkeit zu den Ursprungsmengen anhand des Vorhandenseins in der Ergebnismenge der Operation
herausgefunden werden kann. Die Elemente können in beiden (Schnitt), in mindestens einer
der beiden (Vereinigung) oder exklusiv in einer der beiden (Differenz) Mengen vorhanden sein.
Dies sind genau die Aussagen, die auch für die Konstrukte zweier \textit{Topic Maps} getroffen werden sollen.

\marktopleft{a} \begin{definition}[Vereinigung \cite{HAU73}]
Vereinigungsmenge $M \cup N$ zweier Mengen $M$, $N$ heißt eine Menge genau dann, wenn sie aus allen Elementen besteht,
die der Menge $M$ \textit{oder} der Menge $N$ angehören.
\end{definition}\markbottomright{a}

Die Vereinigung zweier Mengen ist eine Menge, welche alle Elemente enthält, die Teil einer oder beider Ausgangsmengen 
sind. Sollte ein Element in beiden Mengen vorkommen, so ist es auch Teil des Ergebnisses. Es ist zu beachten, 
dass dieses Element nur einmal in der Ergebnismenge vorkommt, denn identische Elemente sind nicht wohlunterscheidbar
und können auch nicht mehrmals Elemente einer Menge sein.

\pagebreak

\marktopleft{a} \begin{definition}[Schnitt \cite{HAU73}]
Der Durchschnitt [bzw. Schnitt] $M \cap N$ zweier Mengen $M$ und $N$ besteht aus allen \mbox{Elementen,}
die \textit{sowohl} $M$ \textit{als auch} $N$ angehören.
\end{definition}\markbottomright{a}

\marktopleft{a} \begin{definition}[Differenz \cite{HAU73}]\label{defSetDiff}
Diese Menge [(Ergebnis der \textit{Differenz})] $M \setminus N$ besteht aus genau den Elementen von $M$, die übrig bleiben, wenn 
man diejenigen Elemente aus $M$ entfernt, die auch Elemente von $N$ sind. Eine derartige 
Menge, auf die dies zutrifft, heißt \textbf{Differenzmenge $M \setminus N$}
der Mengen $M$ und $N$.
\end{definition}\markbottomright{a}

Durch die gegebenen Operatoren für Mengen kann also die Zugehörigkeit der Elemente zu 
den Ausgangsmengen festgestellt werden. Diese Zugehörigkeitsfeststellung ist das, was 
für Topic Maps die Eingangsfragestellung beantworten kann. Deshalb werden nun Operatoren 
definiert, welche an die obigen Mengenoperatoren angelehnt sind. 


\subsection{Definition der Operatoren}\label{opTopMa}

Bei der Betrachtung der Unterschiede von Wissensbasen kristallisieren sich zwei elementar verschiedene Formen der Unterschiedlichkeit heraus.
Zum einen gibt es Unterschiede struktureller Natur und zum anderen können sich als gleich identifizierte Objekte, in ihren 
Eigenschaften unterscheiden. Im Kontext Topic Maps bezieht sich der erste Fall auf das tatsächliche Vorhandensein von 
\textit{Topics} oder \textit{Associations} in den beiden untersuchten \textit{Topic Maps}. Im zweiten Fall werden \textit{Topics}, 
welche als identisch identifiziert wurden, auf Unterschiede in ihren Attributen (\textit{Names}, \textit{Occurrences}, \textit{Identifiers})
hin geprüft. Es entstehen also zwei verschiedene Abstraktionsniveaus oder Betrachtungsebenen, nämlich die strukturelle Ebene 
und die Eigenschaftsebene, auf welcher die jeweiligen Unterschiede zu betrachten sind.\\
Für die strukturelle Ebene werden nun Operatoren definiert, mit denen sich ein mengen\-theoretischer Zugang
zu den Unterschieden und Gemeinsamkeiten von \textit{Topic Maps} eröffnet. Zu den im 
vorigen Kapitel definierten Operatoren für Mengen sollen nun also ähnliche Operatoren 
auch für Topic Maps definiert und nutzbar gemacht werden.
\pagebreak
Wie schon die Unterschiede der \textit{Topic Maps} auf unterschiedlichen Abstraktionsniveaus zu betrachten sind,
so sind auch die Operatoren für unterschiedliche Abstraktionsniveaus zu definieren. 
Die erste Gruppe, angewendet auf ganze \textit{Topic Maps}, gibt einen Überblick über Unterschiede auf
struktureller Ebene, während die zweite Gruppe auf \textit{Topics} \linebreak arbeitet. Warum 
diese Trennung nötig ist, wird im Folgenden erläutert.

\subsubsection{Strukturelle Ebene}\label{semanticLayer}

Die nachfolgend definierten Operatoren arbeiten auf Topic Maps und erzeugen Mengen von
\textit{Topics} und \textit{Associations}. Durch die hohe Komplexität des TMDM ist es notwendig jeweils einzelne Operatoren 
für \textit{Topics} und \textit{Associations} zu definieren. Dies soll an folgendem Beispiel erläutert werden:
\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/AssoziationAMinusAssoziationB}
  \caption{Beispiel für zwei einfache \textit{Topic Maps}}
  \label{graphDiffAssoMitTopicUndTopic}
\end{figure}
Versucht man ganz Intuitiv die (an der Mengentheorie orientierte) Differenz der in \mbox{Abbildung} 
\ref{graphDiffAssoMitTopicUndTopic} dargestellten \textit{Topic Maps}, mit den \textit{Topics} $t_x, t_y$ und der \textit{Association} $a$
als Elemente, zu bilden, so sind wohl die \textit{Association} $a$
und das \textit{Topic} $t_y$ Elemente einer Ergebnismenge $A \setminus B$, da sie Teil der ersten, aber nicht Teil der zweiten \textit{Topic Map} 
sind (s. Def. \ref{defSetDiff}). 


Betrachtet man nun die Definition
der Identität von \textit{Associations} aus Abschnitt \ref{constAndId}, so stellt man fest, dass diese untrennbar an deren 
\textit{Roles} und damit auch untrennbar an deren \textit{Role-Players} gebunden ist. Wird also der
Spieler einer \textit{Association} entfernt, so muss auch die entsprechende \textit{Role} entfernt werden, was wiederum dazu 
führt, dass die Identität der \textit{Association} verändert wird. Somit ist das \textit{Topic} $t_x$ aus \textit{Associations} - Sicht
zwingend Element der Differenz $A \setminus B$. Ist das Topic $t_x$ nun Element der Differenz bedeutet dies
jedoch, dass $t_x$ (mengentheoretisch gesprochen) Element von $A$, jedoch nicht von $B$ ist.
An diesem einfachen Beispiel wird deutlich, dass einfache Operatoren der Art $A \setminus B$ für 
Topic Maps $A$ und $B$ nicht genügen, um alle nötigen Informationen über die strukturellen Unterschiede zweier \textit{Topic Maps} abzubilden. Die 
Lösung des Problems ist eine Aufsplittung des Operators in einen Operator für \textit{Topics} und einen Operator
für \textit{Associations}. Dabei liefern diese Operatoren eine Menge von Konstrukten, welche alle nötigen strukturellen Informationen 
enthalten.

\marktopleft{a} \begin{definition}[$\setminus_t$ - "`strukturelle Topic-Differenz"']\label{semTopicDiff}
Die strukturelle Topic-Differenz einer \textit{Topic Map} $A$ mit den \textit{Topics} $t_i$ und einer \textit{Topic Map} $B$ 
mit den \textit{Topics} $t_j$ ist genau die Menge von \textit{Topics}, welche folgende Bedingung erfüllen: \\
$t_i \in A$ und $t_i \notin B$
\end{definition}\markbottomright{a}

\marktopleft{a} \begin{definition}[$\setminus_a$ - "`strukturelle Association-Differenz"']\label{semAssoDiff}
Die strukturelle Association-Differenz einer \textit{Topic Map} $A$ mit den \textit{Associations} $a_i$ und einer \textit{Topic Map} $B$ 
mit den \textit{Associations} $a_j$ ist genau die Menge von \textit{Associations}, welche folgende Bedingung erfüllen: \\
$a_i \in A$ und $a_i \notin B$
\end{definition}\markbottomright{a}

\marktopleft{a} \begin{definition}[$\cap_t$ - "`struktureller Topic-Schnitt"']\label{semTopicSchnitt}
Der strukturelle Topic-Schnitt einer \textit{Topic Map} $A$ mit den \textit{Topics} $t_i$ und einer \textit{Topic Map} $B$ 
mit den \textit{Topics} $t_j$ ist genau die Menge von \textit{Topics}, welche folgende Bedingung erfüllen: \\
$t_i \in A$ und $t_i \in B$
\end{definition}\markbottomright{a}

\marktopleft{a} \begin{definition}[$\cap_a$ - "`struktureller Association-Schnitt"']\label{semAssoSchnitt}
Der strukturelle Association-Schnitt einer \textit{Topic Map} $A$ mit den \textit{Associations} $a_i$ und einer \textit{Topic Map} $B$ 
mit den  \textit{Associations} $a_j$ ist genau die Menge von \textit{Associations}, welche folgende Bedingung erfüllen: \\
$a_i \in A$ und $a_i \in B$
\end{definition}\markbottomright{a}

\marktopleft{a} \begin{definition}[$\cup$ - "`Merge"']\label{Merge}
Der Merge einer \textit{Topic Map} $A$ in eine \textit{Topic Map} $B$ entspricht den im \cite{TMDM} definierten Merge aller 
mergbaren \textit{Associations} und \textit{Topics} der jeweiligen \textit{Topic Maps}.
\end{definition}\markbottomright{a}

\pagebreak

An dieser Stelle ist zu beachten, dass das Ergebnis dieser Merge-Operation eine nicht nur strukturell zu den
Ausgangs-Maps verschiedene Topic Map ist, sondern auch \mbox{Eigenschaften} der Topics zusammengeführt werden.
Diese Operation stellt somit eine nicht rein strukturelle Operation dar. Im Folgenden werden nun
die Operatoren der Eigenschaftsebene definiert.

\subsubsection{Eigenschaftsebene}
Im vorangegangenen Abschnitt wurden die Unterschiede von \textit{Topic Maps} auf struktureller Ebene
betrachtet. Nun soll untersucht werden, ob sich einzelne Eigenschaften (\textit{Occurrences}, \textit{Names}, ...)
von strukturell äquivalenten \textit{Topics}, unterscheiden. Ob zwei \textit{Topics} auf struktureller Ebene identisch 
sind oder nicht, ist im TMDM definiert. Wenn zwei \textit{Topic Maps} $A$ und $B$ mit \textit{Topics} $t^A_i$ und 
$t^B_j$ gegeben sind, so ist der strukturelle Topic-Schnitt $A \cap_t B$ (Def. \ref{semTopicSchnitt})
eine Menge von \textit{Topics}, für die gilt: $t^A_i \in A, t^B_j \in B$ und $t^A_i = t^B_j$ (nach \cite{TMDM}). Für 
genau diese \textit{Topics} $t^A_i$ und $t^B_j$ gilt es nun zu überprüfen, welche Gemeinsamkeiten und Unterschiede 
auf Eigenschaftsebene bestehen.\\
Es sei erwähnt, dass \textit{Topics}, welche nicht als strukturell gleich
identifiziert wurden, nicht weiter beachtet werden. Dass heißt, sollten zwei nicht identische \textit{Topics} jeweils einen gleichen
\textit{Name} haben, sind diese von vornherein, unabhängig von deren $value$, per Definition
der Identität für \textit{Names} ungleich. Der $parent$ des \textit{Name} ist nämlich ein 
Gleichheitsattribut (s. \ref{defName}), somit wäre der Vergleich zweier strukturell verschiedener \textit{Topics}
immer ein \textit{Topic} ohne Attribute.
Die hier genannten Operatoren sind also für strukturell äquivalente \textit{Topics} definiert:\\

\textbf{Vorbetrachtung}\label{preCond}\\

Für ein Topic $t^A$ sei:
\begin{itemize}
 \item $SI^A$ - die Menge aller \textit{Subject Identifiers} $\{si^A_1, ..., si^A_n\}$
 \item $SL^A$ - die Menge aller \textit{Subject Locators} $\{sl^A_1, ..., sl^A_m\}$
 \item $II^A$ - die Menge aller \textit{Item Identifiers} $\{ii^A_1, ..., ii^A_i\}$
 \item $N^A$ - die Menge aller \textit{Names} $\{n^A_1, ..., n^A_j\}$ 
 \item $O^A$ - die Menge aller \textit{Occurrences} $\{o_1, ..., o_k\}$
 \item $V^A_i$ - die Menge der Variants $\{v^A_1, ..., v^A_l\}$ aller Names $n^A_i$ aus $N^A$
 \item $r^A$ - das reifizierte Konstrukt 
\end{itemize}

\pagebreak

\textbf{Topic Differenz}

\marktopleft{a} 
\begin{definition}[$-$ - "`Topic-Differenz"']\label{topicDiff}
Die Topic-Differenz $t^A - t^B$ zweier semantisch äquivalenter \textit{Topics} $t^A$ und $t^B$ sei ein Tupel $f$ genannt
\textit{Topic} Fragment, mit den folgenden Elementen:\\
$f = (SI, SL, II, N, V, O, r)$, wobei:
\begin{itemize}
  \item $SI := \{si_j \mid si_j \in SI^A$ und $si_j \notin SI^B\}$
  \item $SL := \{sl_j \mid sl_j \in SL^A$ und $sl_j \notin SL^B\}$
  \item $II := \{ii_j \mid ii_j \in II^A$ und $ii_j \notin II^B\}$
  \item $N := \{ n_j \mid n_j \in N^A$ und $n_j \notin N^B\}$
  \item $V := \{ v_j \mid v_j \in V^A_i$ und $v_j \notin V^B_i\}$
  \item $O := \{o_j \mid o_j \in O^A$ und $o_j \notin O^B\}$
  \item $r :=\begin{cases}
		r^A, & \text{wenn } r^A \neq r^B\\
		\text{null, }  & \text{sonst }
	      \end{cases}$
\end{itemize}
\end{definition}
\markbottomright{a}

Das Ergebnis der Topic-Differenz ist ein \textit{Topic} Fragment. Es enthält die in der obigen Definition genannten Elemente, also
alle \textit{Subject Identifier}, \textit{Subject Locator} und \textit{Item Identifier}, welche exklusiv, Eigenschaften des ersten
\textit{Topics} sind. Identifier sind letzt\-endlich URIs, also kann über einen Zeichenkettenvergleich Äquivalenz und somit die Zugehörigkeit
oder Nicht-Zugehörigkeit zum Ergebnis-Fragment festgestellt werden.\\
\textit{Occurrences} werden ebenso wie Identifier behandelt. Sind sie Eigenschaft beider \textit{Topics}, so sind sie nicht Teil des Ergebnisses.
Sind sie ausschließlich Teil des ersten \textit{Topics}, werden sie in das Ergebnis-Fragment aufgenommen.\\ Die Feststellung der Gleich- oder 
Ungleichheit von \textit{Occurrences} beschränkt sich jedoch nicht auf einen Zeichenkettenvergleich, wie dies bei den Identifiern der Fall 
war. Hierzu muss die Definition der Occurrences (Def. \ref{defOccurrence}) und deren Gleichheitsattribute betrachtet werden. Nach dieser 
Definition müssen die Attribute  $value, type, datatype, scope, parent$ auf Gleichheit überprüft werden. $Value$ und $datatype$ sind abermals 
Zeichenketten, $type$ ein \textit{Topic} und $scope$ eine Menge von \textit{Topics}. $Parent$ ist jeweils das \textit{Topic}, zu welchem die 
\textit{Occurrences} gehören, diese sind per Definition gleich. \\
Für \textit{Names} wird aufgrund der Attribute $value, type, scope, parent$ Gleichheit festgestellt. Auch hier werden nur die 
\textit{Names} zum Ergebnis hinzugefügt, welche ausschließlich zum ersten \textit{Topic} gehören.
Die \textit{Variants} der \textit{Names} werden ähnlich zu den schon betrachteten Konstrukten behandelt. Es wird die Identität der 
einzelnen \textit{Variants} geprüft und Überein\-stimmungen werden identifiziert. 
\pagebreak
Da die Definition der Gleichheit von \textit{Variants} 
(Def. \ref{defVar}) besagt, dass u.a. die $parents$ der \textit{Variants} (also deren \textit{Names}) identisch sein 
müssen, ist dies ebenfalls nachzuweisen. Wird Nicht-Gleichheit oder Gleichheit
festgestellt, so wird analog zu den anderen Konstrukten das \textit{Variant} zum Ergebnis-Fragment hinzugefügt oder nicht hinzugefügt.\\
 
\textit{Beispiel}\\

Die gerade formulierte Definition \ref{topicDiff} soll nun noch einmal am Beispiel erläutert werden. (Für die 
Notation beachte man die Vorbetrachtung zu Beginn des Kapitels, gleiche Indizes bedeuten hier Äquivalenz
der entsprechenden Konstrukte)\\

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/topicDiffBsp}
  \caption{Zwei Topics $t^A$ und $t^B$ und deren Differenz}
  \label{graphExampleTopicDiff}
\end{figure}

In Abbildung \ref{graphExampleTopicDiff} sehen wir zwei \textit{Topics} und deren Differenz $t^A - t^B$. 
Voraussetzung für die Differenzbildung ist, dass beide \textit{Topics} äquivalent sind. Definition \ref{defTopic}
besagt, dass zwei \textit{Topics} äquivalent sind, sollten sie in einem \textit{Subject Identifier} übereinstimmen.
Dies ist hier der Fall und somit darf die Topic-Differenz gebildet werden. Das Ergebnis-Fragment enthält nun alle 
relevanten Informationen, welche Unterschiede zwischen den beiden \textit{Topics} bestehen.\\
Alle Identifier, \textit{Names}, \textit{Variants} und \textit{Occurrences}, welche ausschließlich in \textit{Topic} 
$t^A$ vorhanden sind, finden sich nun im angegebenen \textit{Topic}-Fragment wieder. 

Es folgt die Definition des Topic-Schnittes. Die beiden betrachteten Topics müssen wieder 
strukturell äquivalent sein. Es gilt weiterhin die Vorbetrachtung vom
Beginn dieses Abschnittes (Seite \pageref{preCond}).\\

\textbf{Topic Schnitt}

\marktopleft{a} \begin{definition}[$\wedge$  - "`Topic-Schnitt"']\label{topicIntersect}
Der Topic-Schnitt $t^A \wedge t^B$ zweier semantisch äquivalenter \textit{Topics} $t^A$ und $t^B$ sei ein Tupel $f$ genannt
\textit{Topic} Fragment, mit den folgenden Elementen:\\
$f = (SI, SL, II, N, V, O, r)$, wobei:
\begin{enumerate}
  \item $SI := \{si_j \mid si_j \in SI^A$ und $si_j \in SI^B\}$
  \item $SL := \{sl_j \mid sl_j \in SL^A$ und $sl_j \in SL^B\}$
  \item $II := \{ii_j \mid ii_j \in II^A$ und $ii_j \in II^B\}$
  \item $N := \{ n_i \mid n_i \in N^A$ und $ n_i \in N^B \}$
  \item $V := \{ v_j \mid v_j \in V^A_i$ und $v_j \in V^B_i\}$
  \item $O := \{o_j \mid o_j \in O^A$ und $o_j \in O^B\}$
  \item $r :=\begin{cases}
		r^A, & \text{wenn } r^A = r^B\\
		\text{null, }  & \text{sonst }
	      \end{cases}$
\end{enumerate}
\end{definition}\markbottomright{a}

Intuitiv heißt das, dass alle Informationen, die beide \textit{Topics} gemeinsam enthalten, sprich Eigenschaften
von $t^A$ \textit{UND} $t^B$ (deren Schnitt), im Ergebnis-Fragment enthalten sind. Es ist   
die Nähe zu den mengentheoretischen Operatoren zu erkennen. 

Das entsprechende \textit{ODER} der Eigenschaften des \textit{Topics} (also deren Vereinigung) wird durch ein 
Mergen der beiden \textit{Topics} erreicht. Dieser Vorgang ist ausführlich im TMDM beschrieben (s. Def. \ref{Merge}).
  
\subsection{Eigenschaften der Operatoren}

Genau wie die mengentheoretischen Operatoren haben die vorgestellten Topic Maps Operatoren bestimmte Eigenschaften.
Besonders wichtig ist die Kommutativität der Operatoren, da besonders hier Fehler in der Handhabung der vorgestellten Verfahren 
auftreten können. Kommutativität bedeutet Vertauschbarkeit der Operanden miteinander. Aus der Mengentheorie ist bekannt:\\
$A \cap B = B \cap A$ und\\
$A \cup B = B \cup A$\\
Letztendlich agieren die vorgestellten Operatoren auf Mengen, wobei
jedes Element der Menge (wie für Mengen üblich) eine definierte Identität besitzt. 
Der strukturelle Topic Schnitt ( $A \cap_t B$ ) zweier \textit{Topic Maps} ist ein Operator, welcher auf der Menge der 
\textit{Topics} der \textit{Topic Maps} $A$ und $B$ operiert. Die \textit{Topic} Tupel sind dabei die Elemente der Menge. 
Definition \ref{semTopicSchnitt} gleicht der entsprechenden Mengenoperation.
Der Beweis der Kommutativität des Topic-Schnitt Operators lässt sich also auf den Beweis der Kommutativität der 
Schnitt-Operatoren für Mengen zurückführen und ist somit 
trivial. Analog gilt dies natürlich auch für den Association-Schnitt Operator.\\
Die Differenz-Operatoren verhalten sich ebenfalls analog zu ihren mengentheoretischen Entsprechungen. Die Argumentation verläuft 
äquivalent zur vorangegangenen. Die \linebreak mengentheoretische Differenz stellt eine nicht kommutative Operation dar, sprich:\\
$A \setminus B \neq B \setminus A$.\\
Dies gilt auch für die strukturelle Topic - und Association - Differenz.\\
Kommutativität ist auch auf Eigenschaftsebene gegeben. Ein Blick auf die Definitionen \ref{defTopic} und \ref{topicIntersect} zeigt, 
wie auch hier auf einfache Weise Kommutativität nachgewiesen werden kann. Das \textit{Topic} Tupel besteht aus Mengen und dem Reifier.
Für die Mengen sind die Schnittdefinitionen abermals analog zu der entsprechenden mengentheoretischen Ope\-ration festgelegt. Der Reifier
wird beim Schnitt der beiden \textit{Topic Maps} nach den im TMDM zum Mergen festgelegten Regeln behandelt. 
Dass heißt, ist eines der beiden
\mbox{Reified} Konstrukte leer, so wird das andere genutzt. Ist das Element bei beiden leer, so bleibt es auch so. Dass jeweils andere
Konstrukte reifiziert werden, ist per Definition \mbox{ausgeschlossen} (s. Seite \pageref{reification}). Dieser Fall sollte dann bei einer 
technischen Umsetzung gesondert behandelt werden. Ansonsten ist auch hier zu erkennen, dass der Operator kommutativ ist, also die 
\textit{Topics} nach Belieben vertauscht werden können. Für die Vereinigung (also den "`Merge"') der \textit{Topics} gilt natürlich dasselbe 
mit analoger Begründung. Dass die Topic Differenz nicht kommutativ ist, wird anhand der vorangegangen Begründungen sehr einfach 
deutlich und ist deshalb hier nicht noch einmal ausführlich erörtert.\\
Ebenfalls interessant ist die Feststellung der Assoziativität der Operatoren. Sind \mbox{Operatoren} assoziativ, so kann eine Kette von 
Operationen in beliebiger Reihenfolge durchgeführt werden. Für den assoziativen Operator $\circ$ gilt also:\\
$ ( A \circ B ) \circ C \Leftrightarrow A \circ B \circ C \Leftrightarrow A \circ ( B \circ C )$\\
\pagebreak

Auch hier sei wieder ein Blick auf die mengentheoretischen Geschwister der Operatoren vorweggenommen.
Für Mengen $A$, $B$ und $C$ gelten folgende bekannte Gesetzmäßigkeiten:

\begin{itemize}
 \item $ ( A \cup B ) \cup C = A \cup B \cup C = A \cup ( B \cup C ) $,
 \item $ ( A \cap B ) \cap C = A \cap B \cap C = A \cap ( B \cap C ) $,
 \item $ ( A \setminus B ) \setminus C = A \setminus ( B \cup C ) $ und
 \item $ A \setminus ( B  \setminus C ) = ( A \setminus B ) \cup ( A \cap C ) $. \cite{WIKISETRULES}
\end{itemize}

Schnitt und Vereinigung sind also assoziativ, die Differenz jedoch nicht. Die Topic Maps Operatoren verhalten sich erneut genauso, 
wie ihre mengentheoretischen Entsprechungen. Dies folgt direkt aus den oben vorgestellten Erläuterungen
und den Operator\-gesetzmäßigkeiten für Mengen und wird hier nicht noch einmal im Einzelnen erörtert. \linebreak
Allgemein kann nun festgehalten werden, dass sich die Topic Maps Operatoren äqui\-valent zu ihren 
entsprechenden mengentheoretischen Operatoren verhalten.
Sie sind also intuitiv verwendbar und verhalten sich erwartungsgemäß.

\subsection{Differenz von Topic Maps}

Die Topic Map Differenz lässt sich nun mit Hilfe der vorangegangen Betrachtungen, leicht 
definieren:

\marktopleft{a} \begin{definition}[$\setminus$ - Topic Map Differenz]
Die Topic Map Differenz zweier \textit{Topic Maps} $A = (T_a, A_a)$ und $B = (T_b, A_b)$ ist eine \textit{Topic Map}
$M = (T, A)$, für die gilt:
\begin{itemize}
 \item $ T = \{ T_a \setminus_t T_b \} $ 
 \item $ A = \{ A_a \setminus_a A_b \} $ 
\end{itemize}
\end{definition}\markbottomright{a}

Die auf \textit{Topic Maps} definierte Differenz kumuliert nun die zuvor erfolgten Betrach\-tungen auf eine zentrale Operation, welche 
dann eine Übersicht über die strukturellen Unterschiede zweier \textit{Topic Maps} liefert. Atomare Unterschiede sind hier nicht zu 
erwarten, da alle \textit{Topics} und \textit{Associations} im Ergebnis grundsätzlich Subjects modellieren, welche 
ausschließlich in \textit{Topic Map} $A$ vorkommen. Es ist nun also möglich, strukturelle Unterschiede von \textit{Topic Maps} zu erkennen,
jedoch ist eine zentrale Frage noch nicht geklärt. Was bedeutet es, wenn zwei \textit{Topic Maps} gleich sind? 
Der nächste Abschnitt beantwortet diese Frage und es werden die vorgestellten Verfahren und deren Zusammenhänge an einem 
praktischen Beispiel verdeutlicht.

\subsection{Gleichheit von Topic Maps}\label{simOfTM}

Nun wird die Frage nach der Gleichheit von zwei \textit{Topic Maps} noch einmal aufgegriffen.
Zu Beginn der Arbeit wurden verschiedene Ideen für die Gleichheitsbestimmung, wie z.B. das Untersuchen von kanonisch
serialisierten \textit{Topic Maps} mit Hilfe von \mbox{Text-basierten} Differenztools (z.B. UNIX-Diff) vorgestellt.
Die Nachteile dieser Lösungen wurden ebenfalls erörtert. Durch die in der Arbeit definierten Operatoren wird
die Untersuchung der Gleichheit von Topic Maps auf verschiedenen Ebenen möglich. Die Operatoren der strukturellen Ebene
liefern Aussagen über das Vorhandensein von \textit{Topics} und \textit{Associations}. Zwei \textit{Topic Maps}, welche
dieselben Subjects und deren Verknüpfungen \mbox{modellieren}, können durchaus gleich sein, obwohl sich Einzelheiten (z.B. das 
Vorhandensein eines zweiten \textit{Names} eines \textit{Topics}) unterscheiden. Diese Form der Gleichheit sei 
\mbox{\textbf{semantische} \textbf{Gleichheit}} genannt. Sie ist folgendermaßen definiert:

\marktopleft{a} \begin{definition}[$=_s$ - "`semantische Gleichheit"']\label{defSemEq}
 Für zwei \textit{Topic Maps} $A = (T_a, A_a)$ und $B = (T_b, A_b)$ und die leere \textit{Topic Map} 
 $E =(\emptyset, \emptyset)$ sind
 $A$ und $B$ semantisch gleich genau dann, wenn das Ergebnis von deren Topic Map Differenz die 
 leere \textit{Topic Map} ist:\\
 $A =_s B \Leftrightarrow A \setminus_m B = B \setminus_m A = E $
\end{definition}\markbottomright{a}

Sind zwei \textit{Topic Maps} semantisch gleich, so sind in ihnen also dieselben (identischen) \textit{Topics} und \textit{Associations}
vorhanden. Diese Form der Gleichheit ist auch in der Mengentheorie kein unbekannter Begriff. Die Nähe der Topic Maps Operatoren zu denen der 
Mengentheorie ist auch hier wieder sehr praktisch und erleichtert das Verständnis. Der Nachweis über die Gleichheit zweier Mengen 
$A$ und $B$ erfolgt klassisch auf folgende Art und Weise:\\
$A = B \Leftrightarrow (A \subseteq B) \wedge (B \subseteq A)$\\
Mit anderen Worten heißt das, dass $A$ gleich $B$ ist, genau dann, wenn alle Elemente von $A$ in $B$ enthalten sind und alle Elemente aus
$B$ in $A$ enthalten sind, sprich wenn die Differenz der Mengen $A$ und $B$ und der Mengen $B$ und $A$ leer ist. Dass heißt, es gibt keine Elemente
in $A$ bzw. $B$, welche nicht Element von $B$ bzw. $A$ sind. Also:\\
$A = B \Leftrightarrow A \setminus B = B \setminus A = \emptyset$\\
Hier ist nun Definition \ref{defSemEq} eindeutig wiederzuerkennen.\\

\pagebreak

\textit{Beispiel}\\

Man stelle sich zwei verschiedene Fußballfans derselben Mannschaft vor, die Daten über Spieler und Taktiken sammeln. 
Um das Beispiel einfach zu halten, modelliert jeder der beiden Fans jeden der Stammspieler und die Spielerpositionen als \textit{Topic} 
und erstellt \textit{Associations} zwischen dem jeweiligen Spieler und der Position. Da beide Fans dieselben URIs als 
\textit{Subject Identifier} nutzen (Wikipedia Seiten der Spieler und Positionen), lässt sich jeweils feststellen, welche 
\textit{Topics} identisch sind (den selben Spieler repräsentieren). \\
Haben die \textit{Topics} nun auch noch die selben Eigenschaften, also die selben \textit{Names}, \textit{Variants} und
\textit{Occurrences}, so sind die beiden \textit{Topic Maps} vollständig gleich. Dies bedeutet, dass in keiner der beiden
\textit{Topic Maps} mehr oder weniger Informationen, wie z.B. die Größe oder das Gewicht von Spielern oder die durchschnittliche Anzahl
an Toren, die auf einer Position geschossen werden oder aber auch Informationen wie Spitznamen o.ä., zu finden sind. 
Das Zusammenführen der beiden Wissensbasen bringt also
keinen Mehrwert gegenüber einer einzelnen existierenden \textit{Topic Map}.\\
Sind \textit{Topic Maps} somit strukturell gleich und haben deren \textit{Topics} dieselben Attribute, so sind sie 
"`vollständig gleich"'

\marktopleft{a} \begin{definition}[$=_v$ - vollständige Gleichheit]
 Zwei \textit{Topic Maps} $A$ mit den \textit{Topics} $t_a = (SI_a, SL_a, II_a, N_a, V_a, O_a)$ 
 und $B$ mit den \textit{Topics} $t_b = (SI_b, SL_b, II_b, N_b, V_b, O_b)$ 
 sind vollständig gleich, also $A =_v B$ genau dann, wenn:
 
 \begin{itemize}
  \item $A =_s B$
  \item $\forall t_a, t_b \mid t_a = t_b$ gilt: 
    \subitem $SI_a = SI_b$
    \subitem $SL_a = SL_b$
    \subitem $II_a = II_b$
    \subitem $N_a = N_b$
    \subitem $V_a = V_b$
    \subitem $O_a = O_b$
 \end{itemize}
\end{definition}\markbottomright{a}

Die eingangs erwähnten Ebenen der Gleichheit beziehen sich auf die hier definierte \mbox{semantische} und vollständige
Gleichheit. Auf der nun geschaffenen Grundlage lassen sich qualitativ unterschiedliche Aussagen über die Gleichheit von \textit{Topic Maps}
treffen. Einerseits kann völlig abstrahiert von einzelnen Eigenschaften der \textit{Topics} semantische Gleichheit bestimmt werden, 
andererseits besagt die vollständige Gleichheit, dass alle Informationen, die in der einen \textit{Topic Map} vorhanden sind, auch in 
der \mbox{zweiten zu finden sind.}

\newpage
Abschließend noch einmal zurück zu obigem Beispiel:\\

Ein dritter Fan desselben Vereins sammelt ebenfalls Daten im Topic Maps Format. Er kann nun auf einfache Weise bestimmen, welche Subjects 
(Spieler, Positionen) in der ersten und in seiner \textit{Topic Map} korrespondieren (struktureller Topic- und Association-Schnitt) und 
welche er alleine, bzw. welche er noch nicht aufgenommen hat (struktureller Topic- und Association-Differenz). Es ist nun auch einfach 
für ihn möglich nachzuprüfen, welche Daten zu den korrespondierenden Subjects in welchen \textit{Topic Maps} vorhanden sind 
(\textit{Topic}-Schnitt und -Differenz). Auch das Zusammenführen seiner \textit{Topic Map} mit den anderen ist möglich 
(Vereinigung).\\

Die vorgestellten Operatoren sind ein sehr mächtiges Werkzeug zum Vergleich und \mbox{Abgleich} von \textit{Topic Maps}. Es können einfach und
intuitiv Unterschiede und Gemeinsamkei\-ten herausgestellt und verarbeitet werden. Im folgenden Kapitel wird ein prototypisches Framework
vorgestellt, welches die oben definierten Operatoren umsetzt.


\chapter{TMDiff Framework - Entwurf und Implementierung der Operatoren}\label{implementation}

Die im vorigen Kapitel vorgestellten Operatoren für \textit{Topic Maps} sind im Framework \texttt{TMDiff}
umgesetzt. Es soll hier gezeigt werden, dass eine praktische Umsetzung der \linebreak Operatoren möglich ist 
und diese effizient und korrekt funktioniert.\\
Es werden die entwickelten Algorithmen für die einzelnen Operationen und deren Vorteile 
gegenüber einer naiven Implementierung erläutert. Im Anschluss werden das Framework an sich und dessen 
Testkonzept vorgestellt. Systematische Tests stellen korrektes \mbox{Verhalten} der Implementierung 
gegenüber der durch die Tests gegebenen Spezifikation sicher. Es ist Korrektheit für eine gewisse 
Bandbreite an typischen Anwendungsfällen gesichert.\\
\texttt{TMDiff} ist ein Framework, 
welches als solches einfach eingebunden werden kann. Außerdem kann es als eigenständiges Programm verwendet 
oder als Modul in jede beliebige Infrastruktur integriert werden. Wie \texttt{TMDiff} zu verwenden ist, wird
in diesem Kapitel erläutert. Abschließend wird eine Analyse der Performance anhand ausgewählter \textit{Topic Maps}
durchgeführt, was die Effizienz der Implementierung experimentell bestätigen soll.

\section{Algorithmus}

\subsection{Laufzeitabschätzungen}\label{runtimeClasses}

Lang definiert Zeitkomplexität folgendermaßen:
\begin{quote}
Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität.
Die Zeitkomplexität ist eine Funktion $T(n)$ in Abhängigkeit von der Problemgröße $n$.
Der Wert von $T(n)$ ist die Laufzeit des Algorithmus im schlechtesten Fall (worst case), d.h. die Anzahl
der Schritte, die bei einer beliebigen Eingabe höchstens ausgeführt werden. \cite{LANG}
\end{quote}
\pagebreak
Für eine sehr große Problemgröße $n$, lässt sich nun eine Schrankenfunktion $S(n)$ finden, für die gilt:\\
$T(n)$ wächst nicht wesentlich schneller als $S(n)$. 
Mit Hilfe der 
Landau-Symbole \cite{LANDAU}, insbesondere der Groß-O-Notation \cite{BIGO}, lassen sich Algorithmen anhand ihrer \linebreak
Schrankenfunktion hierarchisch klassifizieren.
Die durch die Landau-Symbole gegebenen charakteristischen Schrankenfunktionen definieren obere Schranken für die Laufzeiten 
der betrachteten Algorithmen. Dass heißt, je geringer die kleinste obere Schranke der Laufzeit eines Algorithmus ist, desto schneller
bearbeitet der gegebene Algorithmus das vorliegende Problem (für große Problemgrößen $n)$. Diese Hierarchie der oberen 
Schranken ist in Abbildung \ref{runtimes} dargestellt. 

\begin{figure}[H]
  \centering
  \includegraphics[height=5cm]{Grafiken/RuntimeVenn}
  \caption{Laufzeitklassen von Algorithmen mit Eingabegröße n}
  \label{runtimes}
\end{figure}

Das Ziel des Algorithmenentwurfes soll es sein, eine möglichst niedrige Laufzeit für große Eingaben zu erzielen, 
also in eine möglichst kleine?? Klasse 
aus Abb. \ref{runtimes} zu fallen. Es wird gezeigt (Abschn. \ref{tmdiffAlgo}), dass die obere Schranke des entworfenen Algorithmus durch eine Sortieroperation 
bestimmt ist, welche in der Klasse $O(n\ log\ n)$ liegt \cite{JAVAAPI}. In den folgenden Abschnitten werden die Algorithmen zur
Berechnung der Operationen 
und deren Laufzeitklassifizierung beschrieben.

\subsection{Vorbetrachtung}

\textit{Topic Maps} finden vielseitige Anwendung und können nicht nur zur Modellierung von Ontologien als
Metadaten verwendet werden, sondern auch zum Speichern von Instanzdaten.
Hierbei treten häufig Performanceprobleme auf. Vergleichbar ist die Situation 
mit der relationalen Datenhaltung. Einem relativ kleinen 
Schema, welches zur Strukturbeschreibung 
erstellt wird, stehen viele Instanzdaten gegenüber, auf die über die gegebene Struktur 
zugegriffen werden soll. Auch hier sind effiziente Zugriffstechniken, wie Indexstrukturen, Caching, 
optimierte Join-Bearbeitung, usw. (vgl. \cite{RAHM}) vonnöten, um akzeptable Antwortzeiten zu 
gewährleisten. Es sollen mit den definierten Operatoren solche, unter Umständen große (viele 
\textit{Topics} und \textit{Associations}), \textit{Topic Maps} 
verglichen werden können. Deshalb spielen bei der Implementierung Performanceaspekte 
eine Rolle.
Bei der Bestimmung der Performance eines Algorithmus ist dessen Laufzeit (s. Abschn. \ref{runtimeClasses}) 
ein kritisches Bewertungsmaß. 
Hat ein Algorithmus beispielsweise \mbox{lineare} oder logarithmisch-lineare Laufzeit, so wächst diese
in einem akzeptablen Maße zur Größe der Eingabe (im konkreten Fall die Anzahl
der \textit{Topics} und \textit{Associations}). 
Die folgend vorgestellten Vorgehensweisen sind stark auf das effiziente Berechnen der strukturellen Operatoren
ausgerichtet. Es wird davon ausgegangen, dass die Anzahl der \textit{Occurrences}, \textit{Names} und \textit{Variants}
im Verhältnis zu den \textit{Topics} eine Konstante ist. Es wird also davon ausgegangen, dass \textit{Topics} relativ 
wenige Instanzen der genannten \mbox{Konstrukte} als \mbox{Attribute} besitzen. Bis auf Spezialfälle ist dies keine beschränkende Annahme und
somit ist der kritische Performancefaktor nicht das Berechnen der atomaren Topic-Differenzen und -Schnitte, sondern 
die Berechnung der strukturellen Operationen.
Es werden die einzelnen Schritte der Algorithmen und deren Laufzeitabschätzung aufgezeigt und \linebreak erläutert. 

\subsection{Algorithmus}\label{algorithm}

Zunächst wird ein einfacher Algorithmus beschrieben, welcher korrekt funktioniert, \mbox{jedoch} aufgrund seiner Laufzeit
nicht das Kriterium der Effizienz erfüllt. Dies wird in den folgenden Abschnitten noch genauer erläutert werden.
Für den Algorithmus werden die zwei Operanden bzw. Eingabe-\textit{Topic Maps} $A$ und
$B$ vorausgesetzt. Anhand derer wird das Vorgehen erläutert und der Algorithmus beschrieben.
Im Anschluss wird der im Framework implementierte Algorithmus vorgestellt. Im nächsten Kapitel erfolgt dann ein 
Vergleich der Performance beider Vorgehensweisen, um nachzuweisen, wie effizient die vorgestellte Lösung ist.

\subsubsection{Naiver Algorithmus}\label{naiveAlgo}

Das vorliegende Problem lässt sich prinzipiell einfach lösen. Für die strukturellen Topic-Operationen muss 
jedes \textit{Topic} aus $A$ mit jedem \textit{Topic} aus $B$ verglichen werden. Analog kann auch die Umsetzung
der Association-Operationen erfolgen. \\
\pagebreak

Naiver Algorithmus für das Berechnen des strukturellen Topic-Schnittes:\\
\begin{algorithmic}[1]
  \FOR{jedes \textit{Topic} $t_a$ in $A$}
  \FOR{jedes \textit{Topic} $t_b$ in $B$}
  \IF {$t_a$ = $t_b$}
  \STATE $result.add(t_a)$ 
  \ENDIF
  \ENDFOR
  \ENDFOR
  \RETURN $result$
\end{algorithmic}

\vspace{1em} 

Der strukturelle Association-Schnitt wird analog zu diesem Verfahren berechnet und für die Differenzen muss jedes \textit{Topic}
bzw. jede \textit{Association} hinzugefügt werden, für die kein gleiches Konstrukt in $B$ gefunden wurde. Die Eingabegröße ist
hier jeweils die Anzahl der \textit{Topics} bzw. \textit{Associations}. Somit hat 
diese Vorgehensweise eine quadratische Laufzeit, liegt also in $ O(n^2) $.
Um Skalierbarkeit des Verfahrens sicherzustellen ist quadratische Laufzeit 
unbedingt zu vermeiden, da nun die Laufzeit des Algorithmus in einem großen Verhältnis zur Eingabegröße steigt und sich daraus für
große \textit{Topic Maps} inakzeptable Berechnungszeiten der einzelnen Operationen ergeben.
Deshalb werden in den nächsten Abschnitten optimierte Verfahren vorgestellt und deren Effizienz erläutert.

\subsubsection{TMDiff-Algorithmen}\label{tmdiffAlgo}

\paragraph{Strukturelle Topic-Differenz}~\\
Zunächst werden alle \textit{Topics} der jeweiligen \textit{Topic Maps} $A$ und $B$ mit ihren Identifiern betrachtet. Die Identifier werden 
für $A$ und $B$ einzeln aufgelistet und
lexikographisch aufsteigend sortiert. \textit{Topics} können mehr als einen Identifier haben. Somit ist es möglich, dass in der sortierten Liste
mehr Identifier existieren als \textit{Topics}.
Zu jedem Identifier wird die Zuordnung zum entsprechenden \textit{Topic} erhalten. Es entstehen zwei Listen, eine für 
\textit{Topic Map} $A$ und eine andere für \textit{Topic Map} $B$. Nun wird parallel durch beide Listen iteriert, indem immer ein Vergleich des aktuellen 
Identifiers aus Liste $A$ mit dem Identifier aus Liste $B$ erfolgt. Es wird in der Liste mit dem 
lexikographisch vorangehenden (in lexikographischer Sortierung kleinerem) Identifier fortgeschritten. 
Sollten beide Identifier identisch sein, so wird ein Mapping zwischen den jeweiligen \textit{Topics} erstellt und gespeichert.
Am Ende der Iteration existieren Mappings von \textit{Topics} aus $A$ zu \textit{Topics} aus $B$. \textit{Topics}, 
\pagebreak welche in beiden \textit{Topic Maps} vorkommen
(für die ein Mapping existiert), sind nun nicht Teil 
des Ergebnisses und werden nicht weiter beachtet. Es werden also diejenigen \textit{Topics} aus $A$ 
zur Ergebnismenge hinzugefügt, für die kein
Mapping existiert, welche also in $B$ kein Äquivalent haben. Dies entspricht der Spezifikation der Operation.\\

Der Algorithmus in Pseudocode:
 
\begin{algorithmic}[1]
  \STATE generiere eine lexikographisch sortierte Liste $ids_A$ (bzw. $ids_B$), die alle Identifier der 
  \textit{Topics} aus \textit{Topic Map} $A$ (bzw. $B$) enthält 
  \WHILE{$ids_A$ nicht leer \&\& $ids_B$ nicht leer}
  \IF{$ids_A$.first() < $ids_B$.first()}
  \STATE entferne ersten Identifier aus $ids_A$
  \ELSIF{$ids_A$.first() == $ids_B$.first()}
  \STATE generiere Mapping zwischen den \textit{Topics} mit den Identifiern $ids_A$.first() und $ids_B$.first
  \STATE entferne $ids_A$.first() und $ids_B$.first
  \ELSIF{$ids_A$.first() > $ids_B$.first()}
  \STATE entferne ersten Identifier aus $ids_B$
  \ENDIF
  \ENDWHILE
  \RETURN alle \textit{Topics} aus $A$, für die kein Mapping existiert
\end{algorithmic}
\vspace{1em} 

Die Laufzeitabschätzung für den vorgestellten Algorithmus:

\begin{table}[h]
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{l|p{10.5cm}|X}
\textbf{\#} & \textbf{Beschreibung} & \textbf{Laufzeitklasse}\\
\hline
1 & jeweils lexikographisches Sortieren aller Identifier der Topics beider Maps & $O(n\  log\ n)$\\
2 & paralleles Iterieren der sortierten Listen und Generieren der Mappings & $O(n)$\\
3 & Generieren der Ergebnismenge anhand der Mappings & $O(n)$ \\
  & \textbf{Laufzeitklasse gesamt} & \textbf{O(n log n)}
\end{tabularx}
\caption{Laufzeitabschätzung der Topic Differenz/Schnitt-Berechnung}
\label{topicDiffTable}
\end{table}

Die eigentliche obere Schranke, welche die Laufzeit des Algorithmus begrenzt, 
ist der Sortiervorgang beim Generieren der Listen. Der Teil des Algorithmus, welcher Listen sortiert, liegt in $O(m\  log\ m)$ (\cite{JAVAAPI}), wobei
$m$ die Anzahl der zu sortierenden Elemente, also der Identifier, ist. Es kann davon ausgegangen werden, dass sich die Anzahl der 
Identifier als Konstante verhält. \textit{Topics} haben gewöhnlicherweise wenig Identifier. Somit liegt die Laufzeit für das 
Sortieren weiterhin in $O(n\  log\ n)$, wobei $n$ die Anzahl der \textit{Topics} ist.
Die anderen Schritte durchlaufen die vorher sortierten Listen einmalig und es müssen höchstens $|ids_A| + |ids_B|$ (jeweils Anzahl
der Identifier aller \textit{Topics} in den Eingabe-\textit{Topic Maps}) Vergleiche durchgeführt werden. Im Vergleich zum naiven Algorithmus
zu Beginn des Abschnittes, hat sich beim TMDiff-Algorithmus die Laufzeit auf die Klasse $O(n\  log\ n)$ verringert. 

\paragraph{Struktureller Topic-Schnitt}~\\
Der Algorithmus für die Berechnung des Topic-Schnittes ähnelt dem für die Berechnung der Differenz. Der Unterschied in den Operationen
(vgl. Kap. \ref{opTopMa}) besteht darin, dass nicht die für \textit{Topic Map} $A$ exklusiven, 
sondern die in $A$ und $B$ vorhandenen \textit{Topics} im Ergebnis
enthalten sind. Der Algorithmus für die strukturelle Topic Differenz muss nur geringfügig abgeändert werden, um den Schnitt an Stelle
der Differenz zu berechnen. Beim Generieren der Ergebnisliste werden am Ende jene 
\textit{Topics} ins Ergebnis übernommen, für die ein Mapping existiert. Die Zusammenfassung und Laufzeitabschätzungen sind 
ebenfalls Tabelle \ref{topicDiffTable} zu entnehmen.


\paragraph{Strukturelle Association-Differenz}~\\
Das vorangehend vorgestellte Prinzip des Ordnens der Konstrukte ist für \textit{Associations} nicht adaptierbar, da für sie keine
Identität definiert ist, welche in irgendeiner Form einer Ordnung unterliegt. Ein Sortieren der \textit{Associations} ist also nicht möglich und
somit ein anderes Verfahren für die Berechnung nötig.
Wie in Def. \ref{defAssoc} festgelegt, hängt die Identität einer \textit{Association} von
deren $type$, $scope$ und $roles$ ab. Die  Identität einer $role$ hängt wiederum von deren $player$, $type$ und $scope$ ab. Ist eines
dieser \textit{Topics} einer \textit{Association} aus \textit{Topic Map} $A$ nicht in $B$ vorhanden, so ist dieses eine hinreichende 
Bedingung für das Nicht-Vorhandensein der \textit{Association} in $B$.\\
Dieses Prinzip wird nun ausgenutzt um die Anzahl der möglichen, gleichen \textit{Associations} auf ein Minimum zu reduzieren bzw. das 
Vorhandensein direkt auszuschließen. Es wird, wie bei den Topic-Operatoren, ein Mapping der \textit{Topics} aus $A$ zu ihren äquivalenten
\textit{Topics} aus $B$ erstellt. Nun kann dieses Mapping genutzt werden, um für jede \textit{Association} aus $A$ eine Menge von 
möglichen \textit{Associations} zu erstellen, welche identisch zur jeweiligen, gegebenen \textit{Association} sind.
Diese Menge von \textit{Associations} bestehen im Normalfall aus keiner oder einer (der tatsächlich gleichen) \textit{Association}.
So wird auch für die Associations-Operatoren Skalierbarkeit gewährleistet.

\begin{figure}[H]
  \centering
  \includegraphics[width=\linewidth]{Grafiken/MappingsForTopicsOfAssociation2}
  \caption{Mappings der \textit{Topics} einer \textit{Association} zu den entsprechenden \textit{Topics} in einer zweiten Map}
  \label{mappingsForAssocTopics}
\end{figure}

Wie in Abbildung \ref{mappingsForAssocTopics} dargestellt, werden zu den \textit{Topics}, welche zu $a$ gehören, über das erstellte Mapping
alle gleichen \textit{Topics} in der anderen \textit{Topic Map} herausgesucht. Nun werden für den \textit{Association} Typ $t_z$ 
alle \textit{Associations} in $B$ herausgesucht, die $t_z$ als Typ haben. Gleiches wird für die $role$-Typen und $player$ durchgeführt. Sollte 
es für ein \textit{Topic} aus $A$ mehrere gleiche \textit{Topics} in $B$ geben (in der Abbildung nicht dargestellt), so entstehen Mengen von
\textit{Associations}. Diese Mengen werden nun vereinigt und es bleibt eine Menge möglicherweise gleicher \textit{Associations} zurück
(in Abb. \ref{mappingsForAssocTopics}: $\{ a_{potentiell-1}$, $a_{potentiell-2} \}$). Der letzte Schritt ist dann die konkrete Prüfung auf Gleichheit 
der \textit{Association} aus $A$ mit den \textit{Associations} in 
der Menge der möglichen \textit{Associations} aus $B$. Anzumerken ist hier, dass der Einfachheit halber der $scope$ der \textit{Associations}
und $roles$ in Abb. \ref{mappingsForAssocTopics} jeweils nicht dargestellt wurden. 
Ist also festgestellt worden, dass für $a$ eine gleiche \textit{Association} in $B$ existiert, so ist $a$ nicht Teil des 
Ergebnisses der strukturellen Association-Differenz. Wird kein gleiches Konstrukt gefunden, ist $a$ der Ergebnismenge hinzuzufügen.\\

\pagebreak
Der Algorithmus im Pseudocode:
\begin{algorithmic}[1]
  \STATE generiere Mappings aller \textit{Topics} aus Topic Map $A$ zu semantisch äquivalenten \textit{Topics} aus \textit{Topic Map} $B$
  \FOR{jede \textit{Association} $a$ in \textit{Topic Map} $A$}
  \STATE erstelle Menge $\{a^*_1, a^*_2, a^*_3, ...\}$ von \textit{Associations}, welche aufgrund der \textit{Topics} potentiell äquivalent zu $a$ sind
  \FOR{jede \textit{Association} $a^*$ in $\{a^*_1, a^*_2, a^*_3, ...\}$}
  \IF{$a = a^*$}
  \STATE $assocs.add(a)$
  \ENDIF
  \ENDFOR
  \ENDFOR
  \RETURN $\{a \in A | a \notin assoc\}$ 
\end{algorithmic}
\vspace{1em}

Eine kurze Zusammenfassung und die Laufzeitabschätzung als Übersicht findet sich in Tabelle \ref{assocDiffTable}, wobei
$n$ die Anzahl der \textit{Topics} und $m$ die Anzahl der \textit{Associations} ist. Für Schritt 3 ist die Laufzeit im 
average case ([ac]) angegeben, also die Laufzeit, welche im "`Normalfall"' zu erwarten ist.

\begin{table}[h]
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{l|p{10cm}|X}
\textbf{\#} & \textbf{Beschreibung} & \textbf{Laufzeitklasse}\\
\hline
1 & Generieren der Mappings (Sortierung) & $O(n\ log\ n)$\\
2 & Heraussuchen der möglichen \textit{Associations} $\{a^*_1, a^*_2, a^*_3, ...\}$ für jede \textit{Association} $a$ in \textit{Topic Map A}& $O(m)$\\
3 & Für alle \textit{Associations} $a$: Prüfe ob $a \in \{a^*_1, a^*_2, a^*_3, ...\}$ & $O(m)$ [ac] \\
  & \textbf{Laufzeitklasse gesamt} & \textbf{O(m$+$n log n)}
\end{tabularx}
\caption{Laufzeitabschätzung der Association Differenz/Schnitt-Berechnung}
\label{assocDiffTable}
\end{table}
Zu beachten ist an dieser Stelle, dass sich der Algorithmus im schlechtesten Fall \linebreak quadratisch verhält. Dieser Fall tritt ein, wenn
für jede \textit{Association} in \textit{Topic Map} $A$ jeweils die gesamte Menge von \textit{Associations} als Menge potentiell 
gleicher \textit{Associations} zurückgegeben werden würde. Dieser Fall wäre jedoch eine sehr ungewöhnliche \mbox{Konstruktion} und spielt
für keine anwendungsorientierte \textit{Topic Map} eine Rolle.

\pagebreak

\paragraph{Struktureller Association-Schnitt}~\\
Die Berechnung des strukturellen Association-Schnittes ist ähnlich zur Berechnung der Association-Differenz.  Der Unterschied in den Operationen
(vgl. Kap. \ref{opTopMa}) besteht darin, dass nicht die in \textit{Topic Map} $A$ exklusiv, sondern die in $A$ und $B$ 
enthaltenen \textit{Associations} im Ergebnis
vorhanden sein sollen. Also entspricht das Vorgehen im Prinzip dem o.g. Vorgehen mit dem Unterschied, dass jetzt jene \textit{Associations} 
zurückgegeben werden, für die semantische Äquivalenz festgestellt wurde. Zusammenfassung und die Laufzeitabschätzung sind ebenfalls 
Tabelle \ref{assocDiffTable} zu entnehmen.

\section{Design des Frameworks}

In diesem Abschnitt wird der Aufbau des Programmes \texttt{TMDiff}, welches die im vorigen Kapitel definierten 
Operatoren für Topic Maps umsetzt, beschrieben. Es wird der Aufbau des Frameworks erklärt, wie Korrektheit der Implementierung
sichergestellt wird und wie das Framework eingesetzt bzw. benutzt werden kann.
Zunächst werden die An\-forderungen dargestellt und danach die Umsetzung erläutert.

\subsection{Anforderungen} \label{challengesImpl}

Wie in den vorigen Abschnitten schon genannt, liegt der Fokus der Implementierung auf Korrektheit und 
Effizienz der Umsetzung. Korrektheit kann dabei bis zu einem gewissen Grad durch ein strukturiertes Testkonzept 
gewährleistet werden. Im Abschnitt \ref{tests} wird das Testkonzept im Einzelnen vorgestellt. Softwaretests
können zwar grundsätzlich nicht jeden Fehler verhindern, garantieren jedoch korrektes Verhalten gegenüber den durchgeführten Tests 
und damit für ein gewisses Spektrum an Anwendungsfällen.
Außerdem unterstützen Tests das Erstellen modularer Software, da einzelne Funktionen und Komponenten getestet werden und diese 
Teile dann austausch- und leichter wartbar sind.\\
Effizienz im Sinne der Laufzeit wurde bereits im vorigen Abschnitt diskutiert. Es wurde gezeigt, dass 
die Algorithmen, welche jeweils zur Umsetzung der Operatoren erklärt wurden, in der logarithmisch-linearen Laufzeitklasse
liegen und somit besser sind, als naives Vergleichen jedes \textit{Topics} aus \textit{Topic Map} $A$, mit 
jedem \textit{Topic} aus \textit{Topic Map} $B$.\\
Software sollte
unabhängig von Programmiersprachen und Frameworks verwendbar sein. Das zwingende Festlegen der Anwender auf 
bestimmte Techniken reduziert die Wieder"-verwendbarkeit und Handhabbarkeit der Software. 
Für \texttt{TMDiff} wird ein Java-Interface beschrieben. Außerdem ist die Nutzung als eigenständiges Programm möglich.
Es werden Austauschformate definiert und erläutert. Hiermit können Anwender unabhängig von deren System-Architektur 
und Umgebung auf die Software zugreifen und sie nutzen.
% und sie Nutzen. Solch eine Architektur ist im Kontext von Web Services umgesetzt. \textit{TMDiff} wird als solcher 
% bereitgestellt und im Abschnitt \ref{tmdiffWS} beschrieben.

\subsection{Programmaufbau}
In diesem Abschnitt soll grob der Aufbau des Prototypen für die Berechnung der Ope\-ratoren erläutert werden. 
Dabei wird zunächst das zentrale Interface beschrieben und dann auf die Implementierung eingegangen.

\subsubsection{Voraussetzungen}
Die Implementierung basiert auf der am Topic Maps Lab \cite{TMLAB} entwickelten Topic Maps Engine "`MaJorToM"'.
"`MaJorToM"' steht für "`Merging Java Topic Maps Engine"'. Das Nutzen von "`MaJorToM"' hat einige Vorteile gegenüber
anderen Engines. Sie ist quelloffen und implementiert strikt das Topic Maps Application Programming 
Interface (TMAPI) \cite{TMAPI}. Das TMAPI ist ein in der Topic Maps Welt allgemein anerkannter Standard und 
sichert somit auch die Austauschbarkeit der Backend-Implementierung und damit die Wieder- und Weiterverwendbarkeit
des gesamten Frameworks. \linebreak "`MaJorToM"' ist softwaretechnisch und im tatsächlichen Einsatz (Maiana \cite{MAIA}) \linebreak getestet 
und frei verfügbar. Außerdem hat "`MaJorToM"' noch einen weiteren Vorteil gegenüber anderen Engines. Das im TMDM 
spezifizierte Mergen ist implementiert und selbst innerhalb einer \textit{Topic Map} werden Äquivalenzen automatisch erkannt
und \linebreak aufgelöst. Dadurch, dass die Engine und somit das Backend in Java umgesetzt sind, \mbox{bietet} sich Java als 
Programmiersprache für die Umsetzung des Frameworks an. Außerdem existieren zahlreiche Bibliotheken für Tests, 
komplexe Datenstrukturen und \mbox{Kommunikation}, welche das Entwickeln erleichtern.
%[? history-funktion, transaktionen http://docs.topicmapslab.de/majortom/ ]

\pagebreak

\subsubsection{Interface TMDiff}\label{interfaceSpec}
Im Zentrum des Frameworks steht das Interface \texttt{TMDiff}. Das Interface enthält sieben Methoden, welche die hier vorgestellten 
Operatoren struktureller Assoziationen- und Topic-Schnitt, sowie Differenz und atomarer Topic-Schnitt und -Differenz und zusätz\-lich noch 
die im TMDM spezifizierte Merge-Operation abbildet. \\

\lstset{style=java}
\begin{lstlisting}[language=java]
public interface TMDiff {

  public Set<Topic> semanticTopicDiff(TopicMap tm1, 
      TopicMap tm2);
  public Set<Topic> semanticTopicIntersect(TopicMap tm1, 
      TopicMap tm2);
  public Set<Association> semanticAssociationDiff(
      TopicMap tm1, TopicMap tm2);
  public Set<Association> semanticAssociationIntersect(
      TopicMap tm1, TopicMap tm2);
  public void merge(TopicMap tm1, TopicMap tm2);
  public Fragment topicDiff(Topic t1, Topic t2);
  public Fragment topicIntersect(Topic t1, Topic t2);
  
}
\end{lstlisting}

Die ersten vier Methoden bilden die strukturellen Operationen ab und erwarten als Übergabeparameter zwei 
TMAPI-\textit{Topic Maps}, welche jeweils eine TMDM \textit{Topic Map} repräsentieren. Das Ergebnis sind Mengen
von \textit{Topics} bzw. \textit{Associations}, wie in \mbox{Abschnitt \ref{opTopMa}} spezifiziert.\\
Die Zusammenführung der beiden \textit{Topic Maps} kann mit Hilfe der Merge-Operation \linebreak vollzogen werden. Dies
entspricht der Vereinigung der beiden \textit{Topic Maps}, was auch schon vorher erläutert wurde.\\
Die letzten beiden Methoden bilden die Operationen auf Eigenschaftsebene ab. Auch hier wurde die Funktionalität
ausführlich erläutert. Der Rückgabewert ist ein Fragment-Objekt, welches alle Elemente des \textit{Topic}-Tupels
und die entsprechenden Zugriffsmethoden bereithält.

\pagebreak

\section{Tests}\label{tests}

Mit Hilfe des Testkonzeptes soll das korrekte Arbeiten der Methoden sichergestellt \linebreak werden. Das gewünschte Verhalten der Operatoren
ist im vorigen Kapitel beschrieben worden. Es werden nun für jede Methode eine Reihe von Tests implementiert, die das
Verhalten der Methode gegenüber der Spezifikation des entsprechenden Operators testet und so Korrektheit gegenüber dieser 
Spezifikation gewährleistet.\\
Es wird hierfür das Testframework \textit{JUnit} \cite{JUNIT} verwendet. \textit{JUnit} ermöglicht es auf einfache Art und Weise 
einzelne Softwaremodule, deren Klassen und Methoden zu testen. Dabei fördert es gleichzeitig die Software selbst, modularer zu entwickeln. 
Fehlerisolation, Austauschbarkeit und Verständlichkeit sind Vorteile, die sich unmittelbar daraus ergeben.\\

\subsection{Unit Tests}

Im Framework \texttt{TMDiff} existiert ein eigener Ordner \texttt{src/test} für die Testdateien. Neben Tests von einzelnen, 
kritischen Me\-thoden (im \texttt{utils} Paket) befinden sich hier die sechs Testklassen für die einzelnen Operatoren (die Vereinigung
wird nicht getestet, da diese Funktionalität von der Engine bereitgestellt wird und dort getestet ist).
Beim Unit-Testing wird pro Testfall ein Modul oder Teil der Software getestet.\\
Beispielsweise wird die Methode zum Feststellen der Gleichheit von \textit{Topics} an mehreren Stellen benötigt. Nun wird 
hierfür ein Test geschrieben, welcher das Verhalten der Me\-thode spezifiziert. Daraufhin wird eine Methode implementiert, welche 
ein definiertes Ein- und Ausgabeverhalten aufweist. Die Methode ist für sich gekapselt. Dass heißt, Fehler können leicht isoliert werden.
Außerdem spezifizieren die Tests das Verhalten der Methode. Sie ist somit leicht verständlich und 
austauschbar, sollte sich die Spezifikation des Verhaltens ändern. So wurde beispielsweise in Abschnitt
\ref{identity2} diskutiert, wie die Identität von \textit{Topics} festzulegen ist. Sollte nun eine andere Form der Identität 
festgelegt werden, muss nur eine Methode ausgetauscht und deren Tests angepasst werden. Der Rest der Software bleibt unberührt.\\

\pagebreak

\textit{Beispiel}\\

Das Testkonzept soll am Beispiel des strukturellen Topic-Schnittes erläutert werden. Der strukturelle Topic-Schnitt Operator $\cap_t$ ist
in \texttt{TMDiff} durch die Funktion:\\ 
\texttt{public Set<Topic> semanticTopicIntersect(TopicMap tm1, TopicMap tm2);}\\ 
abgebildet.
Es werden zwei \textit{Topic Maps} an die Methode übergeben und es soll eine Menge von \textit{Topics} zurückgeliefert 
werden, welche die \textit{Topics} enthält, die Teil beider \textit{Topic Maps} sind.
Genau dieses Verhalten wird nun getestet.
Abbildung \ref{testSemanticTopicIntersect} verdeutlicht, welche Fälle dabei zu beachten sind.

\begin{figure}[H]
  \centering
  \includegraphics[height=7cm]{Grafiken/TestTopicMapAagainstTopicMapB}
  \caption{Testsuite für den strukturellen Topic-Schnitt mit Ausgangsmaps und Ergebnis}
  \label{testSemanticTopicIntersect}
\end{figure}

Es müssen Tests für folgende Fälle entwickelt werden:\\
Es gibt in $B$ keine gleichen \textit{Topics} zu dem \textit{Topic} in $A$, es gibt ein \textit{Topic}, welches gleich ist und es
gibt zusätzlich \textit{Topics} in $B$, welche nicht gleich zu einem \textit{Topic} in $A$ sind, welche also nicht im Ergebnis
auftauchen dürfen. Außerdem sollte zusätzlich die Symmetrie der Operation getestet werden, indem man die Operanden vertauscht.
Für die anderen strukturellen Operatoren wird analog vorgegangen. Welches Ergebnis jeweils zu erwarten ist, wurde bereits ausführlich
diskutiert.\\
Die atomaren Topic-Operatoren müssen ebenfalls getestet werden. Hier werden jeweils die Identifier (\textit{Subject Identifier}, \textit{Item
Identifier}, \textit{Subject Locator}) und die Konstrukte \textit{Names}, \textit{Variants} und \textit{Occurrences} miteinander verglichen. Diese
Vergleiche sind Mengenoperationen, da immer eine Menge des jeweiligen Konstrukts
mit dem \textit{Topic} assoziiert ist. Außerdem wird auch das korrekte Behandeln der Reifier getestet. 
Auch hier müssen wieder die oben genannten Fälle für die entsprechenden Mengen unterschieden werden.
\begin{figure}[H]
  \centering
  \includegraphics[width=12cm]{Grafiken/testTopicDiffBsp}
  \caption{Beispiel für das Testen des atomaren Topic-Schnittes anhand der \textit{Subject Identifier} (si - \textit{Subject Identifier}, ii - \textit{Item Identifier})}
  \label{testSemanticAtomicTopicIntersect}
\end{figure}
Das Verfahren, welches für die \textit{Subject Identifier} dargestellt ist, wird dann auch für die anderen Attribute des
\textit{Topics} angewandt und die Tests dementsprechend gestaltet. Beim Vertauschen der Operanden ist ebenfalls das 
gleiche Ergebnis-Fragment zu erwarten, da die atomare Topic-Schnitt Operation symmetrisch ist. \\
Analog hierzu werden die Tests für die atomare Topic-Differenz gestaltet. Was die jeweiligen Ergebnisse der Testfälle 
sind, ist schon bei der Beschreibung der Operationen (Abschn. \ref{operators}) erläutert worden und wird daher hier nicht wiederholt.

\subsection{Integrationstest}

Das Ziel des Integrationstests ist es, die Operationen für komplexe \textit{Topic Maps} zu testen. Komplex bedeutet, 
dass sie viele \textit{Topics} beinhalten, die wiederum über viele \textit{Associations} in Verbindung stehen. 
Es wird z.B. getestet, ob keine Speicherüberläufe für typische Anwendungsszenarien entstehen oder die Software aufgrund
komplexer Zusammenhänge von \textit{Topics} und \textit{Associations} unter Umständen in Endlosschleifen gerät oder 
ähnliches. Außerdem soll gewährleistet werden, 
dass auch bei hochgradig miteinander vernetzten Datensätzen kein unerwartetes Verhalten entsteht und die Implementierung noch 
der gewünschten Spezifikation entspricht.


\subsection{Performancetest}\label{performanceTest}

Der Performancetest soll die absolute und relative Laufzeit der in \texttt{TMDiff} implementierten Algorithmen testen. Dazu wird zunächst die 
absolute Laufzeit des Algorithmus anhand einer Referenz-\textit{Topic Map} bestimmt und dann mit der Laufzeit der naiven Implementierung verglichen.
Leider gibt es zur Zeit keine so ähnlichen Arbeiten, dass ein aussagekräftiger Vergleich durchgeführt werden kann, also bleibt nur der Vergleich 
mit einer Implementierung, welche die selbe Spezifikation erfüllt, jedoch "`offensichtlich"' umgesetzt ist. Eine offensichtliche oder naive 
Umsetzung des Algorithmus spiegelt sich in der Art und Weise der Beschreibung des Algorithmus und der Anzahl der benötigten Codezeilen (LOC) wieder.
Sie ist häufig die erste Herangehensweise für die Problem\-lösung und lässt sich einfach und kurz beschreiben. Häufig ist der so entstandene naive
Algorithmus \mbox{jedoch} nicht die performanteste Lösung für das gegebene Problem.\\
Der Algorithmus für die naive Implementierung wurde bereits in Abschnitt \ref{naiveAlgo} \mbox{erläutert}. Die Ergebnisse der Performancetests
sind in Abschnitt \ref{evalu} dargestellt.

\section{Benutzung}

In diesem Abschnitt soll beschrieben werden, wie \texttt{TMDiff} in eine bestehende Softwareinfrastruktur eingebettet und genutzt werden kann.
Zunächst wird erklärt, wie sich das Framework an sich direkt als Java-Modul einbinden lässt. Danach wird erläutert, wie \texttt{TMDiff} mit Hilfe
von spezifizierten Austauschformaten als Komponente in andere \mbox{Infrastrukturen} eingebunden werden kann.

\subsection{Direkte Einbindung des Java-Frameworks}

Um das Framework direkt in ein eigenes Java Projekt einzubinden, muss zunächst das fertig gebaute JAR unter \cite{JARLOC} heruntergeladen werden.
Danach muss das geladene Paket in den Build-Path des Projektes übernommen werden. Nun lässt sich direkt das in Abschn. \ref{interfaceSpec} 
definierte Interface nutzen. Die Methoden des Interfaces erwarten TMAPI konforme \textit{Topic Maps} bzw. \textit{Topics}. \\
\textit{Topic Maps}, die mit Hilfe einer TMAPI konformen Engine erstellt worden sind, können einfach an die Interface Methoden übergeben werden. Sollte
die \textit{Topic Map} jedoch seri\-alisiert (z.B. als XTM Datei \cite{XTM}) vorliegen, kann diese in eine TMAPI konforme \textit{Topic Map} geparsed 
werden. Hierfür bietet sich beispielsweise TMAPIX \cite{TMAPIX} an. Dazu ist ein Beispiel im Anhang (\ref{minBspTMDiff}) angegeben.

\subsection{Als Programm oder Modul}

Um \texttt{TMDiff} direkt über eine Konsole nutzen zu können, muss das fertig gebaute JAR mit allen Abhängigkeiten heruntergeladen 
werden (unter \cite{FULLJAR}). Außerdem muss Java (Version 6) auf dem ausführenden Rechner installiert sein (siehe \cite{JAVAINST}). 
Sind diese Voraussetzungen erfüllt, wechselt man in der Konsole zu dem Verzeichnis, in dem sich das heruntergeladene Archiv befindet
und startet das Programm folgendermaßen:\\
\texttt{java -jar TMDiffComplete <option> <file1> <file2>}\\
Die beiden (\texttt{<file1>}, \texttt{<file2>}) File-Parameter müssen als Pfade zu den entsprechenden XTM-Topic-Map-Dateien angegeben werden.
Dabei ist \texttt{<file1>} der erste Operand und \texttt{<file2>} der zweite. Der \texttt{<option>}-Parameter kann einer oder mehrere
der folgenden sein:\\
\begin{itemize}
  \item \texttt{-topicDiff} (strukturelle Topic-Differenz)
  \item \texttt{-topicIntersect} (struktureller Topic-Schnitt)
  \item \texttt{-associationDiff} (strukturelle Association-Differenz)
  \item \texttt{-associationIntersect} (struktureller Association-Schnitt)
  \item \texttt{-atomicDiff} (atomare Topic-Differenz)
  \item \texttt{-atomicIntersect} (atomarer Topic-Schnitt)
  \item \texttt{-d <path>} (Pfad zu den Ergebnisdateien)
\end{itemize}
\vspace{1em}

Bei Angabe einer der ersten vier Parameter wird die jeweils aufgeführte strukturelle \linebreak Operation durchgeführt und ein Ergebnis in Form
einer XTM-Topic-Map-Datei zurückgeliefert. Wie das Ergebnis zu interpretieren ist, wird im nächsten Abschnitt erklärt.\\
Werden der fünfte bzw. sechste Parameter gesetzt, so wird für alle Topics, welche sich im strukturellen Topic-Schnitt befinden, jeweils
die atomare Topic-Differenz bzw. der atoma\-re Topic-Schnitt berechnet und das Ergebnis in Form einer XML-Datei zurückgegeben. Die 
Spezifikation des Rückgabeformates ist ebenfalls im nächsten Abschnitt \mbox{erläutert}. Der letzte Parameter erfordert die Angabe
eines Wertes (\texttt{<path>}). Hiermit kann ein Ordner angegeben werden, in welchem die Ergebnisdateien der durchgeführten Operationen
abgelegt werden. Wird dieser Parameter nicht gesetzt, so werden die Dateien in das gleiche Verzeichnis geschrieben, in der sich auch 
das ausgeführte JAR befindet.

\pagebreak

\subsubsection{Spezifikation der Austauschformate}\label{specOfXTMResult}

\textbf{Strukturelle Operationen}\\
Die Ergebnisse der strukturellen Operationen für das Konsolenprogramm \textit{TMDiff}, sind jeweils der XTM2-Spezifikation entsprechende
XML-Dateien. Dass heißt, sie können genauso deserialisiert werden, wie dies auch mit den ursprünglichen XTM-Topic-Map-Dateien der Fall ist. 
Die strukturellen Topic-Operatoren liefern XTM-Topic-Maps mit einer Menge von Topic-Stubs. Topic-Stubs sind hier \textit{Topics}, welche
mindestens einen Identifier haben, über den das \textit{Topic} im ersten Operanden referenziert werden kann. Ist also ein \textit{Topic}
in der Ergebnismenge der jeweiligen Operation enthalten, so ist für dieses \textit{Topic} ein Topic-Stub in der Ergebnis-\textit{Topic Map}
vorhanden. Über diesen Topic-Stub kann nun wieder das ursprüngliche \textit{Topic} gefunden werden. Es werden nur Topic-Stubs und nicht 
komplette \textit{Topics} hinzugefügt, da das Hinzufügen eines \textit{Topics} zu einer \linebreak \textit{Topic Map} häufig das Hinzufügen 
mehrerer anderer \textit{Topics} nach sich zieht. So müssten beispielsweise die Typen der \textit{Occurrences} eines \textit{Topics} 
ebenfalls zur Ergebnis-\textit{Topic Map} hinzugefügt werden, was an dieser Stelle jedoch das Ergebnis verfälschen würde. Mit dem 
Hinzufügen von bloßen Topic-Stubs, die nur Identifier für die Referenz auf das Ursrpungs-\textit{Topic} enthalten, wird dieses Problem 
umgangen.\\
Das Ergebnis der strukturellen Association-Operationen sind ebenfalls valide XTM2-Topic-Map-Dateien, welche jeweils eine Menge
von \textit{Associations} enthalten, die der Spezi\-fikation der jeweiligen Operation entspricht.\\

\textbf{Atomare Operationen}\\
Die atomaren Topic-Operatoren liefern als Ergebnis jeweils XML-Dateien, welche dem in Anhang \ref{resultDTD} gezeigten Schema entsprechen.
Jedes Konstrukt, welches in der Ergebnis-XML-Datei auftaucht, ist eine komplette Referenz auf das entsprechende Konstrukt im ersten 
Operanden der Operation. Das heißt, die Informationen zur Identität der Konstrukte sind vollständig vorhanden. Im Wurzelelement der XML-Datei
befinden sich mehrere \texttt{<topic>}-Elemente, welche jeweils ein Topic-Fragment repräsentieren, also das Ergebnis einer atomaren
Topic-Operation darstellen. (Man beachte, dass die ausgewählte Operation für alle \textit{Topics} in der ersten \textit{Topic Map} mit ihren jeweils
äquivalenten \textit{Topics} in der zweiten \textit{Topic Map} durchgeführt wird.)
Ein Ausschnitt einer solchen Ergebnis-XML-Datei ist im Anhang \ref{exampleXMLResult} gegeben. Das \texttt{<topic>}-Element enthält genau ein 
\texttt{<reference>}-Element, welches ein Attribut (\texttt{si} für \textit{Subject Identifier}, \texttt{sl} für \textit{Subject Locator}, \texttt{ii} für 
\textit{Item Identifier}) hat, dessen Wert auf ein \textit{Topic} in der Ausgangs-\textit{Topic Map} zeigt. Danach folgen jeweils Mengen von 
\texttt{<si>} (\textit{Subject Identifier}), \texttt{<sl>} (\textit{Subject Locator}), \texttt{<ii>} (\textit{Item Identifier}), \texttt{<name>} (\textit{Name}), 
\texttt{<variant>} (\textit{Variant}) und \texttt{<occurrence>} (\textit{Occurrence}) Ele\-menten. Jedes dieser Elemente ist über dessen 
Identität auffindbar. Die \texttt{<parent>}-, \texttt{<type>}- und \texttt{<scope>}-Elemente zeigen über den im Attribut definierten 
Identifier auf die entsprechenden \textit{Topics} und die \texttt{<value>}- bzw. \texttt{<datatype>}-Elemente enthalten die Zeichenkette,
welche auch im entsprechenden Attribut des \textit{Topics} zu finden ist. 

\section{Bewertung}\label{evalu}

Dieser Abschnitt soll die theoretischen Überlegungen zur Leistungssteigerung des entworfenen Algorithmus 
anhand ausgewählter Anwendungsszenarien bestätigen. Wie schon in Abschnitt \ref{relatedWork}
aufgezeigt, existiert keine gleichwertige Umsetzung, mit Hilfe derer ein Vergleich der Performance des Frameworks möglich wäre.
Daher wird der in Abschnitt \ref{naiveAlgo} vorgestellte naive Algorithmus als Referenz implementiert und der relative Laufzeitvergleich
mit der \texttt{TMDiff}-Implementierung als Referenz vollzogen.\\
Die genutzten Testdaten sind zum einen Steve Peppers Italien Opera \textit{Topic Map} \linebreak ("`Opera"' - zu finden unter \cite{MAIOPERA}) und 
zum anderen Uta Schulzes ToyTM \textit{Topic Map} ("`ToyTM"' - zu finden unter \cite{MAITOY}). Opera wurde als Test für die Ontopia
Topic Maps Engine \cite{ONTOENGINE} erstellt und enthält eine Vielzahl verschiedener Konstruktionen. Sie enthält viele 
\textit{Associations} und \textit{Topics} und bietet sich somit
für einen Test der Performance und Korrektheit von \texttt{TMDiff} an. ToyTM enthält im Gegensatz 
dazu weniger \textit{Topics} und \textit{Associations}, ist allerdings auch vielseitig und gut für Tests geeignet.\\
Bei den Performancetests sind drei Anwendungsszenarien von Bedeutung, die im tatsäch\-lichen Einsatz typisch sind:\\

\begin{enumerate}
 \item Vergleich komplett unterschiedlicher \textit{Topic Maps}
 \item Vergleich vollständig gleicher \textit{Topic Maps}
 \item Vergleich geringfügig unterschiedlicher \textit{Topic Maps}\\
\end{enumerate}

Für das erste Szenario werden die Operationen für Opera und ToyTM durchgeführt (es gibt keine gleichen Konstrukte in beiden 
\textit{Topic Maps}). Beim zweiten Szenario werden die Operationen mit zwei vollständig gleichen \textit{Topic Maps} durchgeführt. 
Dazu werden jeweils Opera und ToyTM mit sich selbst verglichen. Für das letzte Szenario wird Opera leicht abgeändert. Es werden zufällig 
einige wenige \textit{Associations} und \textit{Topics} gelöscht. Die so entstandene \textit{Topic Map} Opera(mod) wird nun
mit dem Original verglichen. Es werden also zwei ähnliche 
\textit{Topic Maps} auf Gemeinsamkeiten und Unterschiede hin untersucht.\\
Für alle durchgeführten Operationen ist eine erhebliche Laufzeitverbesserung des TMDiff-Algorithmus gegenüber dem entsprechenden 
naiven Algorithmus zu erwarten. Um welchen Faktor sich die Laufzeit verbessert, ist auch von der Eingabegröße abhängig. Da 
die vorgestellten Algorithmen (naiv und TMDiff) sich in ihrer Laufzeitklasse unterscheiden, ist zu erwarten, dass der Faktor
der Verbesserung bei größerer Eingaben ebenfalls größer wird. So sollte der Vergleich von ToyTM mit sich selbst eine kleinere 
Laufzeitverbesserung erzielen, als der Vergleich von Opera mit sich selbst. Bei der strukturellen Topic Differenz (\textbf{TD})
sollte die Reihenfolge der Operanden keine signifikante Rolle spielen, da jeweils beide Identifier-Listen parallel iteriert werden.
Für den strukturellen Topic-Schnitt (\textbf{TS}) sollte dies ebenso zutreffen. Für die strukturelle Association-Differenz 
(\textbf{AD}) sind die längsten Laufzeiten zu erwarten, da hier für jede potentiell gleiche \textit{Association} ein Vergleich
durchgeführt werden muss. Sollte beim strukturellen Association-Schnitt schon für die erste potentiell gleiche \textit{Association}
eine Übereinstimmung gefunden werden, so ist diese dann Teil des Ergebnisses. Bei der \textbf{AD} sind erwartungsgemäß mehr 
Vergleiche nötig. Außerdem hängen die Association-Operationen stark von der Eingabe ab. Sollten die \textit{Topic Maps} sich 
wenig gleichen (Szenario 3), so tritt das Ausschließen der Möglichkeit einer Übereinstimmung sehr häufig auf und die 
Berechnung ist an dieser Stelle schnell beendet. Im Folgenden werden die gemittelten Laufzeiten der Operationen über jeweils
zehn Versuche in Millisekunden und der Verbesserungsfaktor der Laufzeit von \texttt{TMDiff} im Vergleich zum naiven Algorithmus angegeben.

\pagebreak

\paragraph{Szenario 1}~\\
\begin{table}[h]
\textbf{Opera $\circ$ ToyTm}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 1.198,1 & 1.207,4 & 6.969,2 & 1.222,4\\
TMDiff-Alg. & 65,2 & 64,4 & 155,9 & 63,2 \\
\hline
Faktor~ & 18.38 & 18,75 & 44,70 & 19,34
\end{tabularx}
\caption{Szenario 1: Zeit  in ms für die Operationen anhand von Opera und ToyTM}
\end{table}


\begin{table}[h]
\textbf{ToyTM $\circ$ Opera}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 1.181,4 & 1.180,3 & 7.382,9 & 1.195,4 \\
TMDiff-Alg. & 58,5 & 57,1 & 64,2 & 59,6 \\
\hline
Faktor~ & 20,19 & 20,67 & 115,00 & 20,06
\end{tabularx}
\caption{Szenario 1: Zeit in ms für das Berechnen der Operationen für ToyTM und Opera}
\end{table}

Die bestimmten Laufzeiten für das erste Szenario entsprechen dem Erwartungsbild. Die 
größte Zeiteinsparung ergibt sich für die \textbf{AD}. Hier ist allerdings entscheidend,
in welcher Reihenfolge die Operanden eingesetzt werden. Diese Operation iteriert über alle 
\textit{Associations} aus der ersten \textit{Topic Map}. Da Opera mehr \textit{Associations}
als ToyTM enthält, dauert die Berechnung der Operation in der ersten Variante auch länger.\\
Erwartungsgemäß sollten sich die Laufzeiten für \textbf{TD} und \textbf{TS} beim TMDiff-Algorithmus
nicht unterscheiden. Der hier jedoch vorhandene Unterschied basiert auf dem Vorgehen für
jedes \textit{Topic} in der ersten \textit{Topic Map}, im Mapping nach einem gleichen \textit{Topic}
zu suchen. Somit ist auch hier wieder der erste Operand mit dessen Anzahl an \textit{Topics} entscheidend
für die Laufzeit. Dieser Umstand verbirgt ein geringfügiges Verbesserungspotential, denn es könnte direkt das Mapping 
für die Auswahl der \textit{Topics} genutzt werden.\\

\pagebreak

\paragraph{Szenario 2}~\\
\begin{table}[h]
\textbf{Opera $\circ$ Opera}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 15.105,3 & 15.206,6 & 337.254,7 & 15.132,5 \\
TMDiff-Alg. & 102,5 & 101,8 & 35.616,3 & 103,7 \\
\hline
Faktor~ & 147,37 & 149,38 & 9,47 & 145,93
\end{tabularx}
\caption{Szenario 2: Zeit in ms für das Berechnen der Operationen für Opera}
\end{table}


\begin{table}[h]
\textbf{ToyTM $\circ$ ToyTM}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 127,7 & 127,5 & 377,4 & 123,8 \\
TMDiff-Alg. & 18,7 & 18,6 & 113,6 & 18,7 \\
\hline
Faktor~ & 6,83 & 6,85 & 3,32 & 6,62
\end{tabularx}
\caption{Szenario 2: Zeit in ms für das Berechnen der Operationen für ToyTM}
\end{table}

Hier bestätigt sich ganz eindeutig die eingangs formulierte Vermutung, dass der Ver"-besserungsfaktor 
stark von der Eingabegröße abhängt. Die beiden Tabellen bestätigen nun auch experimentell
die Verbesserung der Laufzeitklasse der TMDiff-Algorithmen. Während für zwei gleiche, kleine 
\textit{Topic Maps} geringe Verbesserungsfaktoren vorliegen (zwischen drei und sieben), liegt 
für zwei größere \textit{Topic Maps} der Faktor höher (zwischen neun und 150). \textbf{TD} und
\textbf{TS} liefern erwartungsgemäß gute Verbesserungsfaktoren. Da für \textbf{AS} bei 
zwei gleichen Eingabe-\textit{Topic Maps} sofort eine entsprechende \textit{Association} gefunden
wird, ist diese Berechnung ebenfalls um einen ähnlichen Faktor schneller als \textbf{TD} und \textbf{TS}.

\pagebreak

\paragraph{Szenario 3}~\\
\begin{table}[h]
\textbf{Opera $\circ$ Opera(mod)}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 15.890,8 & 15.772,4 & 451.111,4 & 17.506,9 \\
TMDiff-Alg. & 103,7 & 105,1 & 45.603,6 & 118,7 \\
\hline
Faktor~ & 153,24 & 150,07 & 9,89 & 147,49
\end{tabularx}
\caption{Szenario 3: Zeit in ms für das Berechnen der Operationen für Italien Opera und Italien Opera(modifiziert)}
\end{table}


\begin{table}[h]
\textbf{Opera(mod) $\circ$ Opera}\\\\
\setlength{\extrarowheight}{.75ex}
\begin{tabularx}{\textwidth}{r|XXXX}
\textbf{$\circ$} & \textbf{TD} & \textbf{TS} & \textbf{AD} & \textbf{AS}\\
\hline
naiver Alg. & 15.588,5 & 15.194,7 & 459.579,8 & 16.249,2 \\
TMDiff-Alg. & 103,6 & 106,2 & 52.640 & 112,1 \\
\hline
Faktor~ & 150,47 & 143,08 & 8,73 & 144,95
\end{tabularx}
\caption{Szenario 3: Zeit in ms für das Berechnen der Operationen für Italien Opera(modifiziert) und Italien Opera}
\end{table}

Auch im dritten Szenario sind merklich Verbesserungen zu verzeichnen. Die besten Verbesserungsfaktoren haben die 
Topic-Operatoren und der \textbf{AS}. Bei der \textbf{AD} müssen wieder mehr \textit{Topics} und \textit{Associations}
betrachtet werden, um sicherzugehen, dass keine gleiche \textit{Association} in der zweiten \textit{Topic Map} vorhanden 
ist.

\paragraph{}

Zusammenfassend lässt sich sagen, dass die entworfenen Algorithmen effizient und korrekt arbeiten. \texttt{TMDiff}
lässt sich einfach in bestehende Java-Anwendungen über das Interface und für alle anderen Anwendungen über die definierten
Austauschformate integrieren. Es sind skalierende Algorithmen entwickelt worden, welche den prak\-tischen 
Einsatz der Operationen auch für große \textit{Topic Maps} ermöglichen. \\
Im nächsten Kapitel erfolgt die Zusammenfassung der Arbeit und deren Ergebnisse und es wird ein Ausblick gegeben,
welche Anwendungs- und Forschungs"-möglichkeiten sich aus den entwickelten Operationen und deren Umsetzung ermöglichen.


\chapter{Ausblick und Zusammenfassung}

In diesem Kapitel wird die Arbeit zusammengefasst. Es wird ein Ausblick für zukünftige Arbeiten gegeben, welche auf 
der hier erstellten Basis aufbauen können. Anschließend wird diskutiert, ob die 
zu Beginn gesteckten Ziele erreicht und die Fragestellung beantwortet wurde.

\section{Ausblick}\label{outlook}

Das effektive Erkennen von strukturellen und atomaren Unterschieden von Wissensbasen in Form von Topic Maps bietet eine Vielzahl von direkten und indirekten \linebreak
Anwendungsmöglichkeiten. Die offensichtlichste Verwendungsmöglichkeit besteht im \linebreak direkten Anwenden der hier vorgestellten Implementierung. 
Es können nun auf einfache Art und Weise Unterschiede und Gemeinsamkeiten aufgezeigt werden. 
Aufbauend hierauf ist es nun möglich, statistische Analysen durchzuführen. Beispielsweise könnte ein Maß der 
Unterschiedlichkeit von zwei \textit{Topic Maps} eingeführt werden. Dadurch ließen sich \textit{Topic Maps} nach Ähnlichkeit
clustern. Eine solche Clusterung könnte weitergehende Analysen erleichtern, da jetzt Daten in einer Referenz-\textit{Topic Map} mit 
Daten von ähnlichen \textit{Topic Maps} (aus einer großen Menge von \textit{Topic Maps}) verglichen werden \mbox{können}. \\ \\
Eine weitere Anwendungsmöglichkeit wäre das Versionsmanagement von \textit{Topic Maps}. Wird eine \textit{Topic Map} dezentral verändert und
sollen diese Veränderungen nun zentral zusammengeführt werden, so muss nur die Differenz der \textit{Topic Maps} und der jeweiligen \textit{Topics} 
berechnet werden. Hieraus können nun einfach Einfüge- und Lösch-Operationen generiert werden. Dieses System funktioniert auch dann, wenn 
mehrere Parteien eine \textit{Topic Map} dezentral bearbeiten. Einfache TMQL-Statements würden beispielsweise \linebreak nicht ausreichen, sobald Konflikte in den 
Änderungen der einzelnen Parteien auftreten (z.B., wenn zwei Parteien das gleiche \textit{Topic} löschen). Beim Durchführen der Operationen werden
solche Probleme erkannt und es wird eine Konfliktauflösung möglich.

\section{Zusammenfassung}

Das Ziel der Arbeit war es ein Verfahren zu entwickeln, um Unterschiede und Gemeinsamkeiten von \textit{Topic Maps} erkennen und 
effizient berechnen zu können. Dazu erfolgte eine mathematische Formalisierung der \textit{Topic Maps} und deren Konstrukte.
So konnten Operatoren definiert werden, welche das Erkennen von Unterschieden und Gemeinsamkeiten einfach ermöglichen. Die definierten
Operatoren sind ähnlich zu den ebenfalls vorgestellten mengentheoretischen Operatoren vielseitig verwendbar und liefern Ergebnisse,
die mit der hier gegebenen Formalisierung der Konstrukte des TMDM konsistent sind. Sie generieren also ein Ergebnis, dessen 
Elemente einer konkret definierten Semantik unterliegen, nämlich derselben Semantik, die über das TMDM für die Operanden 
(\textit{Topic Maps} bzw. \textit{Topics}) der Operationen festgelegt ist. Dies unterscheidet die Arbeit auch in großem Maße von 
bereits bestehenden Umsetzungen, welche Unterschiede ohne semantischen Mehrwert herausfiltern \cite{WANDORA}. \\

Anschließend wurde ein prototypisches Framework entwickelt, welches die spezifizierten Operationen berechnet. 
Die Prämissen der Umsetzung waren Korrektheit gegenüber der genannten Spezifikation 
(Definition der Operatoren Kap. \ref{opTopMa}) und Effizienz im Sinne der Laufzeit (s. Abschn. \ref{challengesImpl}). Das
korrekte Verhalten der umgesetzten Operationen wurde durch ein strukturiertes Testkonzept sichergestellt. Der Algorithmus für die Berechnung und dessen
Laufzeit wurden ausführlich im Abschnitt \ref{algorithm} analysiert und vorgestellt.\\

Abschnitt \ref{evalu} verdeutlicht noch einmal die auf die Performance bezogenen Vorteile der angewandten Algorithmen gegenüber der vorgestellten 
naiven Implementierung (Abschn. \ref{naiveAlgo}). Es wurden vorher theoretische Laufzeituntersuchungen durchgeführt. Die Laufzeiten für 
das Berechnen der Operationen für die ausgewählten Beispiel - \textit{Topic Maps} bestätigen die vorangegangenen Untersuchungen.\\

Zusammenfassend lässt sich sagen, dass die zu Beginn der Arbeit formulierten Fragen beantwortet und mit Hilfe der vorgestellten formal definierten Operatoren ein 
Werkzeug konzipiert wurde, welches über das eigentliche Ziel der Arbeit hinaus (s. Abschn. \ref{outlook}) einen großen Mehrwert für das
Arbeiten mit mehreren \textit{Topic Maps} bietet und neue Anwendungsmöglichkeiten eröffnet.
Mit dem vorgestellten Framework \texttt{TMDiff} ist eine effiziente und leicht benutz- und erweiterbare Umsetzung der Operatoren 
gelungen.


\addcontentsline{toc}{chapter}{Literaturverzeichnis}
%%\nocite{*} %Auch nicht-zitierte BibTeX-Einträge werden angezeigt.
\bibliographystyle{alpha} %Art der Ausgabe: plain / apalike / amsalpha / ...
\bibliography{literatur} %Eine Datei 'literatur.bib' wird hierfür benötigt. 

\begin{appendix}
\gdef\thechapter{\Alph{chapter}}
\chapter{Anhänge}
\gdef\thesection{A.\arabic{section}}

\section{Minimalbeispiel}\label{minBspTMDiff}
\begin{lstlisting}[language=java]
public void topicDiff() throws Exception{
	//the base Locators the new maps should have
	String baseLocator1 = "base1";	
	String baseLocator2 = "base2";
	
	//the file locations of the topic maps
	String fileLocation1 = "xtm-topicmap-1"; 
	String fileLocation2 = "xtm-topicmap-2"; 

	TopicMapSystemFactory fact = TopicMapSystemFactory.newInstance();
	TopicMapSystem sys = fact.newTopicMapSystem();
	
	//create empty maps:
	TopicMap map1 = sys.createTopicMap(baseLocator1);
	TopicMap map2 = sys.createTopicMap(baseLocator2);
	
	//read and paste the xtm-topic-map-files into the empty maps
	XTMTopicMapReader xtmr1 = new XTMTopicMapReader(map1 , new File(fileLocation1));
	XTMTopicMapReader xtmr2 = new XTMTopicMapReader(map2 , new File(fileLocation2));
	xtmr1.read();
	xtmr2.read();
		
	//call TMDiff for the result of any operation
	TMDiff diff = new TMDiffImpl();
	Set<Topic> resultTopics = diff.semanticTopicDiff(map1, map2);
}
\end{lstlisting}
\pagebreak
\section{Ausschnitt eines Ergebnisses eines atomaren Topic-Diff}\label{exampleXMLResult}
\lstset{style=xml}
\begin{lstlisting}
<result>
  ...
  <topic>
    <reference si="http://en.wikipedia.org/wiki/Belgium"/>
    <si>http://en.wikipedia.org/wiki/Belgium</si>
    <si>http://dbpedia.org/resource/Belgium</si>
    <name>
      <parent si="http://en.wikipedia.org/wiki/Belgium"/>
      <type si="http://psi.topicmaps.org/iso13250/model/topic-name"/>
      <value>Kingdom of Belgium</value>
      <scope si="http://psi.oasis-open.org/iso/639/#eng"/>
    </name>
    ...
    <variant>
      <value>Belgien</value>
      <scope si="http://en.wikipedia.org/wiki/short_name"/>
      <scope si="http://psi.oasis-open.org/iso/639/#deu"/>
      <datatype>http://www.w3.org/2001/XMLSchema#string</datatype>
      <name>
        <parent si="http://en.wikipedia.org/wiki/Belgium"/>
        <type si="http://psi.topicmaps.org/iso13250/model/topic-name"/>
        <value>Koenigreich Belgien</value>
        <scope si="http://psi.oasis-open.org/iso/639/#deu"/>
      </name>
    </variant>
    ...
    <occurrence>
      <parent si="http://en.wikipedia.org/wiki/Belgium"/>
      <type si="http://en.wikipedia.org/wiki/Population"/>
      <value>10665867</value>
      <scope si="http://en.wikipedia.org/wiki/Estimation"/>
      <scope si="http://en.wikipedia.org/wiki/2008"/>
      <datatype>http://www.w3.org/2001/XMLSchema#long</datatype>
    </occurrence>
    ...
  </topic>
  ...
</result>

\end{lstlisting}
\pagebreak
\section{Schema für das Ergebnis der atomaren Topic-Operatoren}\label{resultDTD}
\lstset{style=xml}
\begin{lstlisting}
<!ELEMENT result>
<!ELEMENT result (topic*)>

<!ELEMENT topic (reference)>
<!ELEMENT topic (si*)>
<!ELEMENT topic (sl*)>
<!ELEMENT topic (ii*)>
<!ELEMENT topic (name*)>
<!ELEMENT topic (variant*)>
<!ELEMENT topic (occurrence*)>

<!ELEMENT name (parent)>
<!ELEMENT name (type)>
<!ELEMENT name (value)>
<!ELEMENT name (scope*)>

<!ELEMENT variant (value)>
<!ELEMENT variant (datatype)>
<!ELEMENT variant (name)>
<!ELEMENT variant (scope*)>

<!ELEMENT occurrence (parent)>
<!ELEMENT occurrence (type)>
<!ELEMENT occurrence (value)>
<!ELEMENT occurrence (datatype)>
<!ELEMENT occurrence (scope*)>

<!ELEMENT value (#CDATA)>
<!ELEMENT datatype (#CDATA)>

<!ATTLIST parent 	si CDATA sl CDATA ii CDATA > 
<!ATTLIST type 		si CDATA sl CDATA ii CDATA > 
<!ATTLIST scope 	si CDATA sl CDATA ii CDATA > 
<!ATTLIST reference 	si CDATA sl CDATA ii CDATA >
\end{lstlisting}
\end{appendix}

\pagebreak

\section*{Selbständigkeitserklärung}
Der Verfasser erklärt an Eides statt, dass er die vorliegende Arbeit selbständig, 
ohne fremde Hilfe und ohne Benutzung anderer als der angegebenen Hilfsmittel 
angefertigt hat. Die aus fremden Quellen (einschließlich elektronischer Quellen) direkt 
oder indirekt übernommenen Gedanken sind ausnahmslos als solche kenntlich gemacht. Die Arbeit 
ist in gleicher oder ähnlicher Form oder auszugsweise im Rahmen einer 
anderen Prüfung noch nicht vorgelegt worden.

  \vskip 3cm
  Leipzig, {\today}	\hfill Stephan Felke \hfill 



\end{document} 
        
